数据结构期末复习题
练习题：
一、填空题
1、元素项是数据的最小单位，数据元素是讨论数据结构时涉及的最小数据单位。
2、设一棵完全二叉树具有100个结点，则此完全二叉树有49个度为2的结点。
3、在用于表示有向图的邻接矩阵中，对第i列的元素进行累加，可得到第i个顶点的出度。
4、已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有12个叶子
的结点。
n=n0+n1+n2+…+nm (1)
又有除根结点外,树中其他结点都有双亲结点,且是唯一的(由树中的分支表示),所以,有双亲的结点数为：n-1=0*n0+1*n1+2*n2+…+m*nm (2)
联立(1)(2)方程组可得：
叶子数为：n0=1+0*n1+1*n2+2*n3+...+(m-1)*nm
5、有一个长度为20的有序表采用二分查找方法进行查找，共有4个元素的查找长度为3。
6、对于双向链表，在两个结点之间插入一个新结点需要修改的指针共4个。
删除一个结点需要修改的指针共2个。
7、已知广义表LS=(a,(b,c,d),e)，它的深度是2，长度是3。
8、循环队列的引入是为了克服假溢出。
9、表达式a*(b+c)-d/f的后缀表达式是abc+*df/-。
10、数据结构中评价算法的两个重要指标是时间复杂度和空间复杂度。
11、设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是
r->next=s; r=s; r->next=null;
12、设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5，经过
PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是23，而栈顶指针值是1012_H。设栈为顺序栈，每个元素占4个字节。
13、模式串P=‘abaabcac’的next函数值序列为01122312。
14、任意连通图的连通分量只有一个，即是自身。
15、栈的特性是先进后出。
16、串的长度是包含的元素个数。
17、如果一个有向图中没有回路，则该图的全部顶点可能排成一个拓扑序列。
18、在具有n个叶子结点的哈夫曼树中，分支结点总数为n-1。176
19、在线性表的散列存储中，装填因子α又称为装填系数，若用m表示散列表的长度，n表示待散列存储的
元素的个数，则α等于n/m。
20、排序的主要目的是为了以后对已排序的数据元素进行查找。
21、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为O(1),在给定值为
x的结点后插入一个新结点的时间复杂度为O(n)。
22、线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要
移动元素的个数是n/2。
23、两个栈共享空间时栈满的条件top1=top2-1。
24、深度为H 的完全二叉树至少有H个结点；至多有2^H-1个结点；H和结点总数N之间的关系是
H=[log2n]+1。150
25、在有序表A[1…20]中，按二分查找方法进行查找，查找长度为4的元素的下标从小到大依次是1 3 6 8 11
13 16 19
26、设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较7次就可以断定数
据元素X是否在查找表中。
26、数据结构被形式地定义为（D,R），其中D和R 的含义是（D是数据元素的集合，R是数据关系的集合）。
数据的逻辑结构包括哪四种类型（集合类型，线性结构，树形结构，图状结构）。从存储结构的概念上讲，顺序表是线性表的（顺序存储结构），链表是（链式存储结构）。
27、根据初始关键字序列(17，25，3，39，12)建立的二叉排序树的高度为3。
27、算法的五个重要特性有哪些。（有穷性、确定性、可行性、输入、输出）。抽象数据类型是指一个（数学模型）以及定义在该模型上的（一组操作）。
28、设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角上元素）存放在n(n+1)
个连续的存储单元中，则A[i][j]与A[0][0]之间有((i＋１)＊ｉ／２＋ｊ个数据元素。
29、栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为FILO；队列的插入和
删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为FIFO表。
30、设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的前序遍历序列为ABDEF，中
序遍历序列为DBEAFC，后序遍历序列为DEBFCA。
31、如果以链栈为存储结构，则出栈操作时(必须判别栈是否空)，与顺序栈相比，链栈有一个明显的优势是(通
常不会出现栈满的情况)。
32、循环队列采用数组data[1．．n]来存储元素的值，并用front和rear分别作为其头尾指针。为区分队列
的满和空，约定：队中能够存放的元素个数最大为n-l，也即至少有一个元素空间不用，则在任意时刻，至少可以知道一个空的元素的下标是（front）；入队时，可用语句（rear=rear+1%n）求出新元素在数组data中的下标。
33、设一棵完全二叉树有128个结点，则该完全二叉树的深度为8，有65个叶子结点。
33、已知栈的输入序列为1，2，3…．，n，输出序列为a1，a2，…，an，a2=n的输出序列共有（n-1）种输
出序列。
34、设有向图G的存储结构用邻接矩阵A来表示，则A中第i行中所有非零元素个数之和等于顶点i的出度，
第i列中所有非零元素个数之和等于顶点i的入度。
35、将下三角矩阵A[l..8，1..8]的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素
占4个单元，则A[7，5]的地址为（1100）。
36、已知数组A[1..10，1..10]为对称矩阵，其中每个元素占5个单元。现将其下三角部分按行优先次序存
储在起始地址为1000的连续的内存单元中，则元素A[5，6]对应的地址为（1095）。
37、两个串相等的充要条件是，两个串的(长度)相等，且其所对应各个位置的（字符）也相等。
39、在有n个结点的二叉链表中，值为非空的链域的个数为（n-1）。在有n个叶子结点的哈夫曼树中，总结
点数是（2n-1）。在树形结构中，根结点数只有（1），其余每个结点有且仅有一个（前驱）元素结点。40、一棵二叉树L的高度为h，所有结点的度或为0，或为2，则这棵二叉树最少的结点数为(2h-1)。已知二
叉树有50个叶子结点，则该二叉树的总结点数至少是（99）。将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（98）。有64个结点的完全二叉树的深度为( 7)。
41、拓扑排序只能用于（有向无环图）。连通图是指图中任意两个顶点之间（都连通的无向图）。一个有n个
顶点的无向连通图，它所包含的连通分量个数最多为(1)个。任何一个无向连通图的最小生成树（有一棵或多棵）。若含有n个顶点的图形成一个环，则它有（n）棵生成树。
42、求图的最小生成树有两种算法，（普利姆）算法适合于求稠密图的最小生成树，（克鲁斯卡尔）算法适合
于求稀疏图的最小生成树。设图G用邻接表存储，则拓扑排序的时间复杂度为(O(n+e))。
44、从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较，将其放入已排序序列的正
确位置上的方法，称为(插入排序)。对于关键字序列(12，13，11，18，60，15，7，18，25，100)，用筛选法建堆，则开始结点的键值必须为（60）。
33、typedef struct node{int key; struct node *lchild; struct node *rchild;}bitree;
bitree *bstsearch(bitree *t, int k)
{
if (t==0 ) return(0);else while (t!=0)
if (t->key==k)t->lchild=t->rchild=0; else if (t->key>k) t=t->lchild; else t=t->lchild;;
}
34、下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。
void bubble(int r[n])272
{
for(i=1;i<=n-1; i++)
{
for(exchange=0,j=0; j if (r[j]>r[j+1]){temp=r[j+1];__ r[j]=r[j+1]_;r[j]=temp;exchange=1;} if (exchange==0) return； } } 35、下面程序段的功能是实现二分查找算法，请在下划线处填上正确的语句。 struct record{int key; int others;}; int bisearch(struct record r[ ], int k) { int low=0,mid,high=n-1; while(low<=high) { mid=(low+high)/2; if(r[mid].key==k) return(mid+1); else if(r[mid].key } return(0); } 36、设二叉树中度数为0的结点数为50，度数为1的结点数为30，则该二叉树中总共有129个结点数。151 37、设有向图G的二元组形式表示为G =（D，R），D={1，2，3，4，5}，R={r}，r={<1,2>，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>}，则给出该图的一种拓扑排序序列13245。 38、设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则以d=4为增量的一趟希尔排序结束后的结果为49 13 27 50 76 38 65 97。 39、设二叉排序树的高度为h，则在该树中查找关键字key最多需要比较h次. 二、选择题 1、从逻辑上可以把数据结构分为（C ）两大类。 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 2、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（C） (1<=i<=n+1)。 A. O(0) B. O(1) C. O(n) D. O(n2) 3、若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，p N,若p N是n，则p i是( A )。 A. i B. n-i C. n-i+1 D. 不确定 4、已知广义表L=（（x,y,z），a，（u，t，w）），从L表中取出原子项t的运算是（D）。 A. head（tail（tail（L））） B. tail（head（head（tail（L）））） C. head（tail（head（tail（L）））） D. head（tail(head（tail（tail（L）））)） 5、下列陈述中正确的是（D ）。 A.二叉树是度为2的有序树 B.二叉树中结点只有一个孩子时无左右之分 C.二叉树中必有度为2的结点 D.二叉树中最多只有两棵子树，并且有左右之分 6、设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F 中第一棵树的结 点个数是（ A ）。173 A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定 7、．算术表达式a+b*（c+d/e）转为后缀表达式后为（B）。 A．ab+cde/* B．abcde/+*+ C．abcde/*++ D．abcde*/++ 8、关键路径是事件结点网络中（A）。 A．从源点到终点的最长路径 B．从源点到终点的最短路径 C．最长回路 D．最短回路 9、具有12个关键字的有序表，二分查找的平均查找长度（C）。236 A. 2.5 B. 4 C. 3.1 D. 5 10、AVL树是一种平衡的二叉排序树，树中任一结点的（B）245 A.左、右子树的高度均相同 B.左、右子树高度差的绝对值不超过1 C.左子树的高度均大于右子树的高度 D.左子树的高度均小于右子树的高度 11、线性表采用链接存储时，其地址（D）。 A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.连续与否均可以 12、栈和队列是两种特殊的线性表，只能在它们的（B）处添加或删除结点。 Ａ．中间点Ｂ．端点Ｃ．随机存取点Ｄ．结点 13、输入序列为ABC，可以变为BAC时，经过的栈操作为（C）。 A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop 14、下面（ C）不是算法所具有的特性。 Ａ．有穷性Ｂ．确切性Ｃ．高效性Ｄ．可行性 15、下面关于串的的叙述中，（B）是不正确的？ A．串是字符的有限序列 B．空串是由空格构成的串 C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 16、数组A[6][7]的每个元素占五个字节，将其按行优先次序存储在起始地址为1000的内存单元中，则元素 A[3][5]的地址是( A )。117 A. 1130 B. 1180 C. 1205 D. 1210 17、对于一个具有n个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小是（ D）。195 A．n B．(n-1)2 C．n-1 D．n2 18、若广义表A满足Head(A)=Tail(A)，则A为（ B ）。 A．（） B．（（）） C．（（），（）） D．（（），（），（）） 19、堆的形状是一棵 (C )。 A.二叉排序树 B.满二叉树 C.完全二叉树 D.判定树 20、若要在单链表中的结点 *p 之后插入一个结点 *s ，则应执行的语句是 (A ) A．s->next=p->next； p->next=s；B．p->next=s； s->next=p->next； C．p->next=s->next； s->next=p； D．s->next=p； p->next=s->next； 21、链表不具有的特点是（Ｂ）。 A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 22、一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（B）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 23、递归过程或函数调用时，处理参数及返回地址，要用一种称为（Ｃ）的数据结构。 A．队列 B．多维数组 C．栈 D. 线性表 24、设给定权值总数有n 个，其哈夫曼树的结点总数为( Ｄ ) 。 A．不确定 B．2n C．2n+1 D．2n-1 25、若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（Ｃ）。 课件１０６１０７ A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序 26、设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。(Ｃ) A．688 B．678 C．692 D．696 27、若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( D ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 28、设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为 （C）。 (A) 2，3，5，8，6 (B) 3，2，5，8，6 (C) 3，2，5，6，8 (D) 2，3，6，5，8 29、设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（A）。 A q=p->next；p->data=q->data；p->next=q->next；free(q)； B q=p->next；q->data=p->data；p->next=q->next；free(q)； C q=p->next；p->next=q->next；free(q)； D q=p->next；p->data=q->data；free(q)； 30、设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式 成立的是（C ）。 A． N0=N1+1 B. N0=Nl+N2 C. N0=N2+1 D. N0=2N1+l 31、设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，度数为m的结点数为Nm，则 N0=（B）。 A. Nl+N2+……+Nm B. l+N2+2N3+3N4+……+(m-1)Nm C. N2+2N3+3N4+……+(m-1)Nm D. 2Nl+3N2+……+(m+1)Nm 32、设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（A）。 A. aedfcb B. acfebd C. aebcfd D. aedfbc 26、某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是（BB）。 A. 空或只有一个结点 B.高度等于其结点数 C. 任一结点无左孩子 D.任一结点无右孩子 28、下面的说法中正确的是（B）。 (1)任何一棵二叉树的叶子节点在三种遍历中的相对次序不变。 (2)按二叉树定义，具有三个节点的二叉树共有6种。 A．(1)，(2) B．(1) C．(2) D．(1)，(2)都错 29、树有先根遍历和后根遍历，树可以转化为对应的二叉树。下面的说法正确的是（B）。 A．树的后根遍历与其对应的二叉树的后根遍历相同 B．树的后根遍历与其对应的二叉树的中根遍历相同 C．树的先根遍历与其对应的二叉树的中根遍历相同 D．以上都不对 30、.下图的邻接表中，从顶点V1 出发采用深度优先搜索法遍历该图，则可能的顶点序列是（D）。 A. V1V2V3V4V5 B. V1V2V3V5V4 C. V1V4V3V5V2 D.V1V3V4V5V2 31、以下说法不正确的是（ D）。 A．无向图中的极大连通子图称为连通分量 B．连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C．图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D．有向图的遍历不可采用广度优先搜索 32、设哈希表长为14，哈希函数H(key)=key％11，表中已有数据的关键字为15，38，61，84，四个，现将 关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是（D D）。 A．8 B．3 C．5 D．9 34、二维数组A的每个元素是由6个字符组成的串，其行下标i=0，l，...，8，列下标为j=1，2． (10) 设每个字符占一个字节,若按行先存储，元素A[8，5]的起始地址与A按列存储时起始地址相同的元素是（ B）。 A．A[8，5] B．A[3，10] C．A[5，8] D．A[0，9] 35、.在n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（ B）。 A. O(n) B. O(log2n) C. O(nlog2n) D. O(n2) 37、关键路径是事件结点网络中（A A）。 A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最长的回路 D．最短的回路 38、将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（A A）。 A．n B．2n-1 C．2n D．n-1 41、有向图G用邻接矩阵A存储，则顶点i的入度等于A中（B B）。 A. 第i行1的元素之和 B. 第i列1的元素之和 C. 第i行0的元素个数 D. 第i列0的元素个数 42、用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况 如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则所采用的排序方法是（D D） A．选择排序 B．希尔排序 C．归并排序 D．快速排序 43、设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为(A A )。 (A) 10，15，14，18，20，36，40，21 (B) 10，15，14，18，20，40，36，21 (C) 10，15，14，20，18，40，36，2l (D) 15，10，14，18，20，36，40，21 44、设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表中需要做（D） 次线性探测。 A. n2 B. n(n+1) C. n(n+1)/2 D. n(n-1)/2 三、判断题 1．如果两个串含有相同的字符，则这两个串相等。（x ） 2．数组可以看成线性结构的一种推广，因此可以对它进行插入、删除等运算。（ x） 3．二叉树是度为2的树。（x ） 4．在顺序表中取出第i个元素所花费的时间与i成正比。（x ） 5．在栈满情况下不能作进栈运算，否则产生“上溢”。( v ） 6．图G的生成树是该图的一个极小连通子图。（v） 7．所谓数据的逻辑结构指的是数据之间的逻辑关系。（x）数据项 8．二叉排序树的查找和折半查找的时间性能相同。（x） 9．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。 （x） 10．一个有向图的邻接表和逆邻接表中表结点的个数一定相等。（ v） 11、双向链表中至多只有一个结点的后继指针为空。（v） 12、在循环队列中，front指向队列中第一个元素的前一位置，rear指向实际的队尾元素，队列为满的条件是front=rear。（x ） 13、对链表进行插入和删除操作时，不必移动结点。（v ） 14、栈可以作为实现程序设计语言过程调用时的一种数据结构。（v） 15、在一个有向图的拓朴序列中，若顶点a在顶点b之前，则图中必有一条弧 16、对有向图G，如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每个顶点，则该图一定是 完全图。( x ) 17、“顺序查找法”是指在顺序表上进行查找的方法。（ x） 18、向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。（v ） 19、二分查找要求序列顺序存储且关键字序列有序。（v） 20、二路归并时，被归并的两个子序列中的关键字个数一定要相等。（x） 21.调用一次深度优先遍历可以访问到图中的所有顶点。（x） 21．分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。（v） 22．冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（v） 23．满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（v） 24．设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（x） 25．层次遍历初始堆可以得到一个有序的序列。（x） 26．设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。（v） 27．线性表的顺序存储结构比链式存储结构更好。（x） 28．中序遍历二叉排序树可以得到一个有序的序列。（v） 29.快速排序是排序算法中平均性能最好的一种排序。（v） 30．不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。（v ） 31．当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（v） 32．设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为O(log2n)。（v） 33．完全二叉树中的叶子结点只可能在最后两层中出现。（v） 34．哈夫曼树中没有度数为1的结点。（v） 35．对连通图进行深度优先遍历可以访问到该图中的所有顶点。（v） 36．先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（v） 37．由树转化成二叉树，该二叉树的右子树不一定为空。（x） 38．线性表中的所有元素都有一个前驱元素和后继元素。（x） 39.带权无向图的最小生成树是唯一的。（x） 四、应用题 1、已知一棵二叉树的中根序列和后根序列分别为CBEDAFIGH及CEDBIFHGA，请画出这棵二叉树，并给出其先 序序列。 ABCDEGFIH 1、已知一棵二叉树的先根序列和中根序列分别为ABDGHECFIJ及GDHBEACIJF，请画出这棵二叉树，并给出其 后序序列。 GHDEBJIFCA 2、将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果） 3、已知无向图如下所示： （1）．给出从V1开始的广度优先搜索序列；（2）．画出它的邻接表； （3）．画出从V1开始深度优先搜索生成树。 4.假定用于通讯的电文仅有8个字母C1，C2，…，C8组成，各个字母在电文中出现的频率分别为5，15，3，6，22，11，30，8，请先构建一棵哈夫曼树，计算其WPL值，并为这8个字母设计相应的哈夫曼编码 4、假定用于通讯的电文仅有8个字母C1，C2，…，C8组成，各个字母在电文中出现的频率分别为5，25，3，6，10，11，36，4，请先构建一棵哈夫曼树，计算其WPL值，并为这8个字母设计相应的哈夫曼编码。 5、已知一表为（Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec）,按表中顺序依次插入初始为空的二叉排序树，要求： (1)画出建立的二叉排序树（值的大小以字母顺序为准）。 (2)对该二叉排序树作中序遍历，试写出遍历序列。 (3)求出在等概率情况下查找成功的平均查找长度。 6、已知一个图的顶点集V和边集G分别为： V={0,1,2,3,4,5,6,7}; E={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10, (4,6)4,(5,7)20}; 按照普里姆算法从顶点0出发得到最小生成树，试写出在最小生成树中依次得到的各条边。 (0,1),(0,3),(0,2),(1,5),(3,6),(6,4),(5,7)。 7、设一哈希表长为13，采用线性探测法解决冲突，哈希函数H(key)=key%13, （1）画出在空表中依次插入关键字25，20，34，15，21，32，29，82，57后的哈希表。 （2）求在等概率情况下，查找成功和查找不成功的平均查找长度。 7、已知散列函数为H(K)=K mod 11,健值序列为{47，7，29，11，16，92，22，8，3}哈希表长为11，采用线性探测法处理冲突，试构造闭散列表，并计算查找成功和不成功的平均查找长度。 8、已知待排序的序列为（403，187，312，61，818，170，857，272，633，442），试完成下列各题。 (1) 根据以上序列建立一个堆（画出第一步和最后堆的结果图），希望先输出最小值。 (2) 输出最小值后，如何得到次小值。（并画出相应结果图）。 8、已知待排序的序列为（503，87，512，61，908，170，897，275，653，462），试完成下列各题。 (1) 根据以上序列建立一个堆（画出第一步和最后堆的结果图），希望先输出最小值。 (2) 输出最小值后，如何得到次小值。（并画出相应结果图）。 9、下图表示一个地区的交通网，顶点表示城市，边表示连结城市间的公路，边上的权表示修建公路花费的 代价。怎样选择能够沟通每个城市且总造价最省的n-1条公路，画出一个方案。 10、已知图G=（V, E ），其中V={v1,v2,v3,v4,v5}, E={ 11、设有关键码序列{19，32，40，13，30，24，35}，请给出平衡二叉树的构造过程（只需要给出不平衡时到平衡的过程即可）。 11、设有关键码序列{20，35，40，15，30，25，38}，请给出平衡二叉树的构造过程（只需要给出不平衡时到平衡的过程即可）。 12、已知散列函数为H(K)=K mod 13,健值序列为12，31，15，54，04，78，22，29，34，54，29，47，采用拉链法处理冲突，试构造开散列表，并计算查找成功的平均查找长度。 12、已知散列函数为H(K)=K mod 13,健值序列为13，41，15，44，06，68，12，25，38，64，19，49，采用拉链法处理冲突，试构造开散列表，并计算查找成功的平均查找长度。 13、对于下列一组关键字36，48，25，55，80，17，11，72，试写出快速排序每一趟的排序结果。 13、对于下列一组关键字46，58，15，45，90，18，10，62，试写出快速排序每一趟的排序结果。 10,15,18,45,46,58,62,90 14、对下面的关键字集（30，14，25，43，35，27，64，49），若查找表的装填因子为0.8，采用线性探测再散列解决冲突：（1）设计哈希函数；（2）画出哈希表；（3）求查找成功的平均查找长度。 14、在如下数组A 中链接存储了一个线性表，表头指针为A [0].next ，试写出该线性表。 data next v 2 v 4 v 1 v 5 v 3 v 6 16 21 11 14 33 6 19 18 6 5 线性表为：（78，50，40，60，34，90） 15、按顺序输入下列顶点对: (V1, V2)、(V1, V6)、(V2, V6)、(V1, V4)、(V6, V4)、(V1, V3)、(V3, V4)、 (V6, V5)、(V4, V5)、(V1, V5)、(V3, V5)。（顶点序列为：V1，V2，V3，V4，V5，V6） （1）画出相应的邻接表。 （2）写出在邻接表上，从顶点3开始（表下标从0开始）的DFS序列和DFS生成树 五、算法与程序设计 1、阅读算法完成题目要求： （1）说出下列算法的功能。 template struct Binnode { T data; Binnode bool Unknown (Binnode { Binnode p=first->next; q=first->prior; while(p!=q && p->prior!=q) if(p->data==q->data) { p=p->next; q=q->prior; } else return 0; return 1; }//判断双链表的对称性 算法功能： （2）根据下列算法和输入的数据画出生成的链表形式。 template LinkList { first=new Node Node first->next=NULL;; for (int i=0; i { cin>>x; s=new Node s->next=first->next; first->next=s; } } 输入数据为：1 2 3 4 5 6 输出结果为： （3）说出下列算法的功能，它是采用什么结构实现的。 template void BiTree { const int MaxSize = 100; int front = 0; int rear = 0; BiNode if (root==NULL) return; else{ Q[rear++] = root; while (front != rear) { q = Q[front++]; cout< if (q->lchild != NULL) Q[rear++] = q->lchild; if (q->rchild != NULL) Q[rear++] = q->rchild; } } } 算法功能：二叉树的层序遍历对列 （4）阅读下列算法求出调用该算法后输出结果。 void AE(Stack& S) { InitStack(S); Push(S,30); Push(S,40); Push(S,50); int x=Pop(S)+2*Pop(S); Push(S,x); int i,a[4]={5,8,12,15}; for(i=0;i<4;i++) Push(S,a[i]); while(!StackEmpty(S)) cout< } 输出结果为： （5）设有一个正整数序列组成的非递减有序单链表，阅读下面的算法，指出该算法的功能，并在“//后面加 上必要的注释。 void F1(Linklist L;int,x){ p= L→next; q=p; //p为工作指针 pre=L; L→next=NULL; .//q指最小元素 while(P&&P→data r=p→next; p→next=L→next; L→next=p; p=r; //（2）置逆 }//while q→next=p; pre=q; //（3）重新链接 }//F1 算法功能：在单链表中将比正整数X小的数按递减次序排序 （6）设有一个由正整数组成的无序单链表，阅读下面的算法，指出该算法的功能。 void F1(Linklist &L){ p=L→next; pre=p; //pre为最小结点指针 while(p){ if(p→data pre=p; p=p→next; //（1）查找最小值结点 }//while printf(pre→data); //（2）输出最小值结点 if(pre→next && pre→data%2==0) //如果最小节点的下一个接点是偶数就删除 { p=pre→next, pre→next=p→next;free(p); //（3）删除其后继结点 }//if }// F1 算法功能： （7）阅读下列算法：（设L是带头结点的单链表的头指针，并为已知的LinkList类型）void DeleteX(LinkList &L){ p=L－>next; while(p&& p－>next－>data!=x){ q=p;p=p－>next; } if(p){ q－>next=p－>next; free(p); } } 算法的功能：删除单链表L中值为X的结点的直接前驱结点 2、程序设计 (1)设有一单链表L，结点结构为编写算法判断该单链表L中的元素是否成等差关系，即： 设各元素值次为a1,a2,a3,…,a n，判断a i+1-a i=a i-a i-1是否成立。若是返回1，否则返回0。 函数说明为：int dengcha(Node (2)写出二分查找的非递归算法。(要求统计查找过程中元素的比较次数) 函数说明为： int binsearch(int r[ ], int n,int k)； (3)设单链表以非递减有序排列，设计算法实现在单链表中删除值相同的多余结点。 函数说明为：Void Linklist::purge(Node （3） template Void purge(Node { Node *p,*q; P=first->next; While(p->next) If(p->data==p->next->data) { q=p->next; p->next=q->next; delete q; } Else p=p->next; } (4)写出图在邻接表存储结构下广度优先的遍历算法。函数说明为： template 函数说明为：void ALGraph ::BFSTraverse(int v)； （5）编写计算二叉树最大宽度的算法（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。 （6）设计有向图（AOV网）在邻接表存储结构下的拓扑排序算法。 template 函数说明为：void ALGraph :: TopSort( )； （6）假设哈希函数为H（key）,编写用链地址法解决冲突的哈希表的插入和删除算法。 void F2( HashTable &H, keytype Key){//哈希表插入，用链地址法解决冲突 i=H(Key);;// 获取哈希地址 if(H[i]==Null){ s=(Linklist)malloc(sizeof(Lnode)); s→data=key; s→next=H[i]; H[i]=s; }//if else{ p=H[i];// 查找 while(p&&p→data!=key) p=p→next; if(p→data==key) exit(1); else{ s=(Linklist)malloc(sizeof(Lnode));// 产生新结点，插入表头 s→next=H[i]; H[i]=s; }// else }//else }//F2 void Delete_HS(HashTable &H, KeyType key){ //哈希表删除，用链地址法解决冲突 i=H(key); //获得哈希地址 if(H[i]= =Null) exit(1); p=H[i];q=p; // p为工作指针，q为p前趋 while(p&&p→data!=key) {//查找 q=p; p=p→next; }//while if(!p) exit(1); if(q==H[i]){ //key为第一结点 H[i]p→next; free(p); }// if else{ q→next=p→next; free(p); }//else }//Delete_HS （7）设计在链式存储结构上交换二叉树中所有结点左右子树的算法。 typedef struct node {int data; struct node *lchild,*rchild;} bitree; void swapbitree(bitree *bt) { bitree *p; if(bt==0) return; swapbitree(bt->lchild); swapbitree(bt->rchild); p=bt->lchild; bt->lchild=bt->rchild; bt->rchild=p;} 2017年数据结构期末考试题及答案 一、选择题（共计50分，每题2分，共25题） 1 ?在数据结构中，从逻辑上可以把数据结构分为 C 。 A. 动态结构和静态结构B?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2?数据结构在计算机内存中的表示是指 A ° A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D .数据元 素之间的关系 3.在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A. 逻辑B?存储 C.逻辑和存储 D.物理 4 .在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C ° A.数据的处理方法B?数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5. 在决定选取何种存储结构时，一般不考虑 A ° A.各结点的值如何B?结点个数的多少 C?对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6. 以下说法正确的是D ° A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据可以有相同的逻辑结构 7. 在以下的叙述中，正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出 8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一 个结点，则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点 的双循环链表 11. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点（由p所指向）满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点 数据结构期末考试题及答案 、选择题 1.在数据结构中, 从逻辑上能够把数据结构分为 A. 动态结构和静态结构 B ．紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2. 数据结构在计算机内存中的表示是指 A.数据的存储结构 B.数据结构 C.数据的逻辑结构 D.数据元素之间的关系 3. 在数据结构中, 与所使用的计算机无关的是数据的 结构。 A.逻辑 B.存储 C.逻辑和存储 D.物理 4. 在存储数据时, 一般不但要存储各数据元素的值, 而且还 要存储C A. 数据的处理方法 B. 数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5.在决定选取何种存储结构时般不考虑A 。 A. 各结点的值如何 B. 结点个数的多少 C.对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6.以下说法正确的是 A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据能够有相同的逻辑结构7．算法分析的目的是C , 算法分析的两个主要方面是A 。 (1) A.找出数据结构的合理性 和输出的关系 C. 分析算法的效率以求改进 档性 ( 2) A .空间复杂度和时间复杂度 C. 可读性和文档性 性 8. 下面程序段的时间复杂度是 s = 0; for( I = 0; i v n; i + + ) for( j = 0; j v n; j ++ ) s +二B[i][j]; sum = s ; 9. 下面程序段的时间复杂度是 for( i = 0; i v n; i + + ) for( j = 0; j v m; j ++ ) B .研究算法中的输入 C .分析算法的易读性和文 B .正确性和简明性D .数据复杂性和程序复杂 O( n2) 。 O( n*m) 。 试卷 A 1、顺序表中所有结点的类型必须相同。（） 2、链接表中所有灵活利用存储空间，所以链表都是紧凑结构。 ( ） 3、用Ch1，Ch2表示两个字符，若Ord(Ch1)＜Ord(Ch2)，则称Ch1＜Ch2 4、Shell排序方法是不稳定的。（） 5、只允许最下面的二层结点的度数小于2的二叉树是完全二叉树( ) 6、若检索所有结点的概率相等，则内部路径长度大的二叉树其检索效 率高。（） 7、n个结点的有向图，若它有n(n－1)条边，则它一定是强连通的。 8、广义表中，若限制表中成分的共享和递归所得到的结构是树结构） 9、多维数组元素之间的关系是线性的。（） 10、任何无环的有向图，其结点都可以排在一个拓扑序列里。 ( ) 11、数据的逻辑结构可形式地用一个二元组B＝(K，R)来表示，其中K 是__________，R是_____________。 12、广义表(a,(a,b),d,e,((i,j),k))的长度是。 13、一个串，除自身之外的所有子串都是该串的。 14、树形选择排序总的时间开销为。 15、按先根次序法周游树林正好等同于按周游对应的二叉 树。 16、外部路径长度E定义为从扩充二叉树的到每个 的路径长度之和。 17、在图结构中，如果一个从V p到V q的路径上除V p和V q可以相同外， 其它结点都不相同，则称此路径为一称为回路。 18、栈是一种表。 19．带权的又称为网络。 20、n×n的三对角矩阵按“行优先顺序”存储其三对角元素，已和a11 的存储地址为LOC(a11)，矩阵的每个元素占一个存储单元，则a ij(i＝1， j=1，2或1＜i＜n，j＝i－1，i，i＋1或i＝n，j＝n－1，n)的存储地 址为LOC(a ij)＝。 第二章算法分析 1.算法分析是计算机科学的基础 2.增长函数表示问题（n）大小与我们希望最优化的值之间的关系。该函数表示了该算法的时间复杂度或空间复杂度。增长函数表示与该问题大小相对应的时间或空间的使用 3.渐进复杂度：随着n的增加时增长函数的一般性质，这一特性基于该表达式的主项，即n 增加时表达式中增长最快的那一项。 4.渐进复杂度称为算法的阶次，算法的阶次是忽略该算法的增长函数中的常量和其他次要项，只保留主项而得出来的。算法的阶次为增长函数提供了一个上界。 5.渐进复杂度：增长函数的界限，由增长函数的主项确定的。渐进复杂度类似的函数，归为相同类型的函数。 6.只有可运行的语句才会增加时间复杂度。 7. O() 或者大O记法：与问题大小无关、执行时间恒定的增长函数称为具有O（1）的复杂度。 增长函数阶次 t(n)=17 O(1) t(n)=3log n O(log n) t(n)=20n-4 O(n) t(n)=12n log n + 100n O(n log n) t(n)=3n2+ 5n - 2 O(n2) t(n)=8n3+ 3n2O(n3) t(n)=2n+ 18n2+3n O(2n) 8.所有具有相同阶次的算法，从运行效率的角度来说都是等价的。 9.如果算法的运行效率低，从长远来说，使用更快的处理器也无济于事。 10.要分析循环运行，首先要确定该循环体的阶次n，然后用该循环要运行的次数乘以它。（n 表示的是问题的大小） 11.分析嵌套循环的复杂度时，必须将内层和外层循环都考虑进来。 12.方法调用的复杂度分析： 如：public void printsum(int count){ int sum = 0 ; for (int I = 1 ; I < count ; I++) sum += I ; System.out.println(sun); } printsum方法的复杂度为O（n）,计算调用该方法的初始循环的时间复杂度，只需把printsum方法的复杂度乘以该循环运行的次数即可。所以调用上面实现的printsum方法的复 杂度为O（n2）。 13指数函数增长> 幂函数增长> 对数函数增长 《数据结构与算法》（c语言版）期末考复习题 一、选择题。 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。（1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O(n2) 。 s =0; for( I =0; i 2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（A） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B） A.（100,80,90,60,120,110,130） B.（100, 120, 110,130,80, 60,90） C.（100,60,80,90,120,110,130） D.（100,80, 60,90, 120, 130,110） 9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（B ） A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（D） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序 数据结构期末考试试题及答案 、选择题 评价一个算法时间性能的主要标准是()。1. A、算法易于调试 B、算法易于理解 C、算法的稳定性和正确性 D、算法的时间复杂度 )等五个特性。计算机算法具备有输入、输出、 2. A、可行性、可移植性和可扩充性 B、可行性、确定性和有穷性 C、确定性、有穷性和稳定性 D、XX、稳定性和XX 。带头结点的单链表head为空的判定条件是()3. A、h ead==NULL B、h ead->next==NULL C、head->next==head D、head！=NULL 以下关于线性表的说法不正确的是()。4. A、线性表中的数据元素可以是数字、字符、记录等不同类型。 B、线性表中包含的数据元素个数不是任意的。 C、线性表中的每个结点都有且只有一个直接前趋和直接后继。 D、存在这 样的线性表：表中各结点都没有直接前趋和直接后继。 在顺序表中，只要知道()，就可在相同时间内求出任一结点的存储地址。 5.A、基地址 B、结点大小 C、向量大小 D、基地址和结点大小 ()运算中，使用顺序表比链表好。6. A、插入 B、删除 C、根据序号查找 D、根据元素值查找一个长度为n的顺序表中，向第i个元素之前插入一个新元素时，需要向后移动()个元素7.A、n-i B、n-i+1 C、n-i-1 D、i ()适合作为经常在首尾两端操作线性表的存储结构。8. A、顺序表 B、单链表 C、循环链表 D、双向链表 栈和队列的共同点是() 9. A、都是先进后出 B、都是先进先出 C、只允许在端点处插入和删除元素 D、没有共同点 一个队列的入列序列是1234，则队列的输出序列是()。10. A 、4321 B 、12 3 4 C 、1432 D 、 3241队列与一般的线性表的区别在于()。11. A、数据元素的类型不同 B、运算是否受限制 C、数据元素的个数不同 D、逻辑结构不同 假上溢”现象会出现在()中。12. A、循环队列 B、队列 C、链队列 、顺序队列D.二、填空 2017《数据结构》期末考试试题及答案 《数据结构》期末考试试题及答案 1 ................................................................. 2..试题 1 答案............................................................ 7..《数据结构》期末考试试题及答案 2 ................................................................. 9..试题 2 答案........................................................................ 1.. 4. 《数据结构》期末考试试题及答案 3 ............................................................... 1..6试题 3 答案........................................................................ 2.. 1. 数据结构》期末考试试题及答案 1 单选题（每题 2 分，共 20 分） 1. 栈和队列的共同特点是 （ ）。 A. 只允许在端点处插入和删除元素 B. 都是先进后出 C. 都是先进先出 D. 没有共同点 2. 用链接方式存储的队列，在进行插入运算时 （ ）. A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D .头、尾指针可能都要修改 3. 以下数据结构中哪一个是非线性结构？ （ ） A. 队列 B. 栈 C. 线性表 D. 二叉树 4. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644（io ）, A[2][2]存放 若有18个元素的有序表存放在一维数组 A[19]中，第一个元素放A[1]中, 现进行二分查找，则查找 A [3]的比较序列的下标依次为（ A. 1 ， 2， 3 B. 9， 5， 2， 3 C. 9， 5， 3 D. 9， 4， 2， 3 8. 对n 个记录的文件进行快速排序，所需要的辅助存储空间大致为 A. O （1） B. O （n ） C. O （ 1 og 2n ） D. O （n2） 9. 对于线性表（ 7， 34， 55， 25， 64， 46， 20， 10）进行散列存储时，若选 用 H （K ）=K %9 作为散列函数，则散列地址为 1 的元素有（ ）个， 位置在 676（10），每个元素占一个空间， 表示用 10 进制表示。 问 A[3][3] （10）存放在什么位置？脚注 （10） 5. A ．688 B ．678 C ． 692 D ． 696 树最适合用来表示 （ ）。 A.有序数据元素 B.无序数据元素 6. C.元素之间具有分支层次关系的数据 D .元素之间无联系的数据 二叉树的第 k 层的结点数最多为 （ ）. A ．2-1 B.2K+1 C.2K-1 D. 2k-1 7. 第 1 页，共 11 页 任课教师签名： 命题教师签名： 系主任签名： 主管院长签名： 湛江师范学院2007年－2008学年度第1学期 期末考试试题A 卷 (考试时间:120分钟) 考试科目： 数据结构 请将所有答案填写在答题卡上，交卷时请将所有试卷上交 一、单选题(每小题2分，共40分) 1．下列算法的时间复杂度是（ B ）。 for ( i=0; i 6．栈的特点是（B ）。 A 先进先出 B 后进先出 C 后进 后出 D 不进不出 7．经过下列运算后GetHead(Q)的值是（ A ） InitQueue(Q); EnQueue(Q,a); EnQueue(Q,b); A a B b C 1 D 2 8．一维数组的元素起始地址loc[0]=1000，元素长度为4，则loc[2]为（ C ）。 A 1000 B 1010 C 1008 D 1020 9．二叉树第i层上最多有（ C ）个结点。 A 2i B 2i-1 C 2i-1 D i2 10．满二叉树（ A ）二叉树。 A 一定是完全 B 不一定是完全 C 不是 D 不是完全 11．二叉树按二叉链表存储，每个结点包含三个域（lchild、data、rchild），若p指针指向二叉树的根结点，经过运算while ( p->rchild!=null ) p=p->rchild，则（ A ）。 A p指向二叉树的最右下方的结点 B p指向二叉树的 最左下方的结点 C p仍指向根结点 D p为null 12．在具有n个结点的完全二叉树中，结点i(2i 广东创新科技职业学院期末考试试题（标明A 卷、B 或C 卷） 2018 —2019 学年第二学期考试科目：《数据结构》 (闭（开）卷 90分钟) 院系____________ 班级____________ 学号___________ 姓名 __________ 一、选择题（每小题 2 分，共 40 分） 1.计算机识别、存储和加工处理的对象被统称为（）。 A ．数据 B ．数据元素 C ．数据结构 D ．数据类型 2.数据结构指的是数据之间的相互关系，即数据的组织形式。数据结构一般包括（）三方面内容。 A ．数据的逻辑结构、数据的存储结构、数据的描述 B ．数据的逻辑结构、数据的存储结构、数据的运算 C ．数据的存储结构、数据的运算、数据的描述 D ．数据的逻辑结构、数据的运算、数据的描述3．数据的逻辑结构包括（）。 A ．线性结构和非线性结构 B ．线性结构和树型结构 C ．非线性结构和集合结构 D ．线性结构和图状结构 4.（）的特征是：有且仅有一个开始结点和一个终端结点，且所有结点都最多只有一个直接前驱和一个直接后继。 A ．线性结构 B ．非线性结构 C ．树型结构 D ．图状结构 5. 评价一个算法时间性能的主要标准是（）。 A ．算法易于调试 B ．算法易于理解 C ．算法的稳定性和正确性 D ．算法的时间复杂度 6. 下述程序段①中各语句执行频度的和是（）。 s=0; ① for(i=1;i<=i;j++) s+=j; A ．n-1 B ．n C ．2n-1 D ．2n 7. 下面程序段的时间复杂度为（）。 for(i=0;i 贵州大学理学院数学系信息与计算科学专业 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 一、单项选择题 1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。 (A)、正确性(B). 可行性(C). 健壮性(D). 输入性 2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（）。 for(i=n-1；i>=0；i--) for(j=0；j 2005年－2006学年第二学期“数据结构”考试试题（A） 姓名学号(序号)_ 答案隐藏班号 要求：所有的题目的解答均写在答题纸上（每张答题纸上要写清楚姓名、班号和学号），需写清楚题目的序号。每张答题纸都要写上姓名和序号。 一、单项选择题（每小题2分，共20分） 1．数据的运算a 。 A.效率与采用何种存储结构有关 B.是根据存储结构来定义的 C.有算术运算和关系运算两大类 D.必须用程序设计语言来描述 答：A。 2. 链表不具备的特点是 a 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C.不必事先估计存储空间 D.所需空间与其长度成正比 答：参见本节要点3。本题答案为：A。 3. 在顺序表中删除一个元素的时间复杂度为 c 。 A.O(1) B.O(log2n) C.O(n) D.O(n2) 答：C。 4．以下线性表的存储结构中具有随机存取功能的是 d 。 A. 不带头结点的单链表 B. 带头结点的单链表 C. 循环双链表 D. 顺序表 解 D。 5. 一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是 c 。 A.edcba B.decba C.dceab D.abcde 答：C。 6. 循环队列qu的队空条件是 d 。 A. (qu.rear+1)%MaxSize==(qu.front+1)%MaxSize B. (qu.rear+1)%MaxSize==qu.front+1 C.(qu.rear+1)%MaxSize==qu.front D.qu.rear==qu.front 答：D。 7. 两个串相等必有串长度相等且 b 。 A.串的各位置字符任意 B.串中各位置字符均对应相等 C.两个串含有相同的字符 D.两个所含字符任意 答：B。 8. 用直接插入排序对下面四个序列进行递增排序，元素比较次数最少的是c 。 A.94,32,40,90,80,46,21,69 B.32,40,21,46,69,94,90, 80 C.21,32,46,40,80,69,90,94 D.90,69,80,46,21,32,94, 40 答：C。 9. 以下序列不是堆（大根或小根）的是 d 。 A.{100,85,98,77,80,60,82,40,20,10,66} B.{100,98,85,82,80, 77,66,60,40,20,10} C.{10,20,40,60,66,77,80,82,85,98,100} D.{100,85,40,77,80, 60,66,98,82,10,20} 2012年数据结构期末考试题及答案 一、选择题 1．在数据结构中，从逻辑上可以把数据结构分为C。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指A。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的A结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储C。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑A。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是D。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是C，算法分析的两个主要方面是A。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O（n2）。 s ＝0； for（I ＝0；i＜n；i＋＋） for（j＝0；j＜n；j＋＋） s ＋＝B[i][j]； sum ＝s ； 9．下面程序段的时间复杂度是O（n*m）。 for（i ＝0；i＜n；i＋＋） for（j＝0；j＜m；j＋＋） A[i][j] ＝0； 10．下面程序段的时间复杂度是O（log3n）。 i ＝0； while（i＜＝n） i ＝i * 3； 11．在以下的叙述中，正确的是B。 A．线性表的顺序存储结构优于链表存储结构 B．二维数组是其数据元素为线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出 12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B 。 A．数据元素具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 13．链表不具备的特点是A。 A．可随机访问任一结点B．插入删除不需要移动元素 C．不必事先估计存储空间D．所需空间与其长度成正比 14．不带头结点的单链表head为空的判定条件是A。 《数据结构》试题（A卷） （考试时间： 90分钟） 一、单项选择题（本大题共15小题，每小题2分，共30分） （每题只有一个选项是正确的,将答案填写在括号内，错选、多选不得分） 1.（）是组成数据的基本单位，是一个数据整体中相对独立的单元。 A．数据 B.数据元素 C.数据对象 D.数据结构 2.算法计算量的大小称为算法的（）。 A.效率????? B.复杂度 C.数据元素之间的关系??? ? D.数据的存储方法 3.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入或删除运算，则采用以下（）方式最节省时间。 A.链式存储 B. 索引存储 C.顺序存储 D.散列存储 4.下述哪一条是顺序存储结构的优点？（） A.存储密度大? B.插入运算方便? C.删除运算方便? D.可方便地用于各种逻辑结构的存储表示 5.在一个单链表中，若删除p所指结点的后续结点，则执行（）。 >next=p->next->next >next=p->next =p->next;p->next=p->next->next =p->next->next 6.带头结点的单链表head为空的判定条件是（）。 ==NULL >next==NULL >next==head !==NULL 7.非空的循环单链表head的尾结点(由p所指向)满足（）。 >head==NULL ==NULL >next==head ==head 8.下面关于线性表的叙述中，错误的是哪一个？（） A.线性表采用顺序存储，必须占用一片连续的存储单元。 B.线性表采用顺序存储，便于进行插入和删除操作。 C.线性表采用链式存储，不必占用一片连续的存储单元。 D.线性表采用链式存储，便于插入和删除操作。 9.队列操作的原则是（）。 A.后进先出 B.先进先出 C.只能进行插入 D.只能进行删除 10.栈中允许进行插入和删除的一端称为（）。 A.栈首 B.栈尾 C.栈顶 D.栈底 11．假设以数组A[n]存放循环队列的元素，其首尾指针分别为front和rear，则当前队列中的元素个数为（）。 A．（rear-front+n）%n B. rear-front+1 C. (front-rear+n)%n D.(rear-front)%n 12.最大容量为n的循环队列，队尾指针是rear，队首指针是front，则队空的判断条件是（ ）。 A.（rear+1）%n==front ==front +1==front D.(rear-1)%n==front 13.将一个十进制的数转换成二进制的数，可以使用以下一种称为（）的数据结构。 A. 图 B. 树 C. 广义表 D. 栈 14. 把一棵树转换为二叉树后，这棵二叉树的形态是（）。 A. 有2种 B. 有3种 C. 有4种 D. 唯一的 15.一棵左右子树均不空的二叉树在先序线索化后，其中空链域的个数是（）。 A. 3 B. 2 C. 0 D. 不确定 二、填空题（本大题共10个空，每空2分，共计20分） 《数据结构》期末考试题型及分值 （1）简答题6题*5分=30分简要回答要点 （2）分析题6题*5分=30分给出结果 （3）设计题1题*10分=10分设计思想及结果 （4）编程题1题*10分=10分完整代码 （5）综合题1题*20分=20分抽象数据类型的定义、表示、实现、算法分析{定义=功能（ADT）表示=存储结构体实现=算法（基本操作）算法分析=时间、空间复杂度} 考试概念有：1.数据结构{一、线性表（栈-队-列-串-数组-广义表-逻辑结构-存储结构-运算结构） 二、非线性表（集合-树-图）} 2.抽象数据类型数据对象-数据关系-基本操作 3.算法性质-要求（设计）-效率（度量） 4.实例查找：高效查找算法 排序：高效的排序算法 分析题考试题目参考 （1）1-2-3-4-5-6顺序建BBST （2）6-5-4-3-2-1顺序建BBST 简答题实例 （1） （2） 数据结构试卷（一） 三、计算题（每题 6 分，共24分） 1. 在如下数组A 中链接存储了一个线性表，表头指针为A [0].next ，试写出该线性表。 A 0 1 2 3 4 5 6 7 data 60 50 78 90 34 40 next 3 5 7 2 0 4 1 线性表为：（78，50，40，60，34，90）??????? ?? ???????01 1 1 1010111011101010111 2. 请画出下图的邻接矩阵和邻接表。 3. 已知一个图的顶点集 V 和边集E 分别为： V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15, 数据结构复习题 一、单选题(每小题2分，共12分) 1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。 A． HL＝ps p一>next＝HL B． p一>next＝HL；HL＝p3 C． p一>next＝Hl；p＝HL； D． p一>next＝HL一>next;HL一>next＝p； 2．n个顶点的强连通图中至少含有( )。 A.n—l条有向边 B.n条有向边 C.n(n—1)／2条有向边 D.n(n一1)条有向边 3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A.O(1) B.O(n) C.O(1Ogzn) D.O(n2) 4．由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。 A．24 B．48 C． 72 D． 53 5．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。 A.整形 B.引用型 C.指针型 D.常值引用型· 6．向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )。 A．O(n) B．O(1) C．O(n2) D．O(10g2n) 二、填空题(每空1分，共28分) 1．数据的存储结构被分为——、——、——和——四种。 2．在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为——域和——域。 3．——中缀表达式 3十x*(2.4／5—6)所对应的后缀表达式为————。 4．在一棵高度为h的3叉树中，最多含有——结点。 5．假定一棵二叉树的结点数为18，则它的最小深度为——，最大深度为——· 6．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定——该结点的值，右子树上所有结点的值一定——该结点的值。 7．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层——调整，直到被调整到——位置为止。 8．表示图的三种存储结构为——、——和———。 9．对用邻接矩阵表示的具有n个顶点和e条边的图进行任一种遍历时，其时间复杂度为——，对用邻接表表示的图进行任一种遍历时，其时间复杂度为——。 10．从有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素时，其查找长度分别为——和——· 11．假定对长度n＝144的线性表进行索引顺序查找，并假定每个子表的长度均为，则进行索引顺序查找的平均查找长度为——，时间复杂度为——· 12．一棵B—树中的所有叶子结点均处在——上。 13．每次从无序表中顺序取出一个元素，把这插入到有序表中的适当位置，此种排序方法叫做——排序； 每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做——排序。 14．快速排序在乎均情况下的时间复杂度为——，最坏情况下的时间复杂度为——。 三、运算题(每小题6分，共24分) 1．假定一棵二叉树广义表表示为a(b(c，d)，c(((，8)))，分别写出对它进行先序、中序、后序和后序遍历的结果。 先序： 中序； 后序： 2．已知一个带权图的顶点集V和边集G分别为： V＝{0，1，2，3，4，5}； 《数据结构》期中试卷（2009级） 2010-2011学年第一学期姓名：学号：成绩： 一、选择题：（每小题2分，共20分） 1.有六个元素6，5，4，3，2，1 的顺序进栈，下列哪一个不是合法的出栈序列？（） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 2.在一个有125个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（） 个元素。 A．8 B. 62.5 C. 62 D. 7 3. 已知广义表A＝((a,b,c),(d,e,f),(h,(i,j)),g)，从A表中取出原子项e的运算是：( ) A.head(tail(A)) B.head(tail(tail(A))) C.head(head(tail(tail(A)))) D.head(tail(head(tail(A)))) 4.循环队列存储在数组A[0..m]中，设front和rear分别为队列的头指针和尾指针，则入队 时的操作为（）。 A. front=( front +1) mod (m+1) B. rear=(rear+1) mod (m+1) C. front=( front +1) mod m D. rear=(rear+1) mod m 5. 在双向循环链表中,在p指针所指向的结点前插入一个指针q所指向的新结点,其修改指针 的操作是( ) (假设双向循环链表的结点结构为(llink,data,rlink)。A．p->llink=q； q->rlink=p；p->llink->rlink=q；q->llink=q； B．p->llink=q；p->llink->rlink=q ；q->rlink= p；q->llink=p->llink； C．q->rlink=p；q->llink=p->llink；p->llink->rlink=q; p->llink=q; D．q->llink=p->llink；q->rlink=p；p->llink=q；p->llink=q； 6. 一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。 A．250 B．500 C．254 D．以上答案都不对 7. 已知一棵二叉树的前序遍历结果为ABCDEF, 中序遍历结果为CBAEDF, 则后序遍历的结果 为（）。 A．CBEFDA B．FEDCBA C．CBEDFA D．不定 8. 利用二叉链表存储树时，则根结点的右指针是（）。 A．指向最左孩子B．指向最右孩子C．空D．非空 9.设有二维数组A[0..9, 0..19], 其中每个元素占两个字节，第一个元素的存储地址为100， 若按列优先顺序存储，则元素A[6,6]存储地址为( )。 A. 252 B. 132 C. 352 D.232 10. 引入二叉线索树的目的是（） A．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除 C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一 东莞理工学院城市学院（本科）试卷（B卷） 2016 -2017 学年第二学期 开课单位：计信系，考试形式：闭卷，允许带入场 科目：数据结构班级：15级软件工程1∽6班，姓名：学号： 一、填空题（每题2分，共12分） 1、数据结构在计算机中基本存储方式有结构和结构。 2、栈(又称为堆栈)是操作受限的线性结构，其操作的基本原则是，插入和删除元素的一端称为。 3、深度为k（根的深度为1）的完全二叉树至少有_______ ____个结点，至多有________ _____个结点。 4、对于一个有n个顶点的完全无向图，具有条边；而对于一个有n个顶点的完全有向图，具有条弧。 5、在进行排序时，最基本的操作是和。 6、哈希函数是一种映象，是从到的一种映象。 二、单项选择题（请将答案写在题目后的括号中。每题2分，共40分） 1、下面结构中，不属于数据逻辑结构的是（）。 （A）线性链表（B）树形结构 （C）线性结构（D）网状结构 2、下面说法正确的是（）。 （A）数据元素是数据的最小单位 （B）数据项是数据的基本单位 （C）数据结构是带有结构的各数据项的集合 （D）上述说法都是错误的 3、有下列算法，其时间复杂度是（）。 x=1 ; while (x<=n) x=x*2 ; } （A） O(n) （B） O(n2) （C） O(㏒2n) （D） O(n㏒2n) 4、线性表若采用链式存储结构，要求内存中可用存储单元的地址是（）。 （A）必须是连续的（B）部分地址必须是连续的 （C）一定是不连续的（D）连续或不连续都可以 5、设p是非空单链表中结点q的直接前驱结点，删除q的正确操作是（）。 （A） p->next=q->next；free(p) ; （B） p->next=q->next；free(q) ; （C） q->next=p->next；free(p) ; （D） q->next=p->next；free(q) ; 6、栈和队列的共同点时（）。 （A）都是先进先出（B）都是后进先出 （C）只允许在端点处插入和删除元素（D）没有共同点 7、设有一个栈顶指针为top的顺序栈S，top为0时表示栈空，则向堆栈S中压入一个元 素x执行的操作是（）。 （A） S[top++]=x；（B） S[++top]=x； （C） S[--top]=x；（D） S[top--]=x； 8、设循环队列Q的最多元素个数为m，队尾指针是rear，队首指针是front，则队列为满的条件是（）。 （A） == ；（B） != ；2017年数据结构期末考试题及答案A
数据结构期末考试题及答案
数据结构期末试题1及答案
数据结构复习资料,java数据结构期末考试
(完整版)数据结构(c语言版)期末考试复习试题
《数据结构》期末考试题及答案
数据结构期末考试试题及答案
2017数据结构期末考试试题及答案
数据结构期末考试试题A卷(完成,不知对不对)
《数据结构》期末考试试卷
数据结构期末考试试题及答案
数据结构期末考试试题含答案
2015年数据结构期末考试题及答案
数据结构期末考试试题和标准答案及评分标准
数据结构期末考试复习总结
大学数据结构期末考试试题(有答案)
2010年数据结构期中考试试卷及答案
《数据结构》期末考试卷-b卷
- 数据结构期末测试题及答案
- 2020年数据结构期末考试题及答案A
- (word完整版)2017年数据结构期末考试题及答案A,推荐文档
- 数据结构期末考试试题A答案
- 大学数据结构期末考试试题(有答案)
- 数据结构期末考试试题及答案1
- 数据结构期末考试试题A卷
- 数据结构期末考试试题及复习资料
- 数据结构期末考试试题及答案
- 数据结构期末考试试题及答案
- 2017《数据结构》期末考试试题及答案
- 数据结构期末考试试题
- 2017《数据结构》期末考试试题及答案
- 2017年数据结构期末考试题及答案A
- 数据结构期末考试试题(含答案)
- 2010年数据结构期中考试试卷及答案
- 《数据结构》期末考试试卷
- 大学数据结构期末考试试题(有答案)
- 数据结构期末考试试题及答案
- 2017数据结构期末考试试题及答案