数据结构试卷及参考答案_9
数据结构试卷（九）
一、选择题(30分)
1．下列程序段的时间复杂度为（）。
for(i=0；i for(i=0；i (A) O(m*n*t) (B) O(m+n+t) (C) O(m+n*t) (D) O(m*t+n) 2．设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（）个元素。 (A) n-i (B) n+l -i (C) n-1-i (D) i 3．设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为（）。 (A) N1-1 (B) N2-1 (C) N2+N3 (D) N1+N3 4．利用直接插入排序法的思想建立一个有序线性表的时间复杂度为（）。 (A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(1og2n) 5．设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（）。 (A) p->right=s；s->left=p；p->right->left=s；s->right=p->right； (B)s->left=p；s->right=p->right；p->right=s；p->right->left=s； (C) p->right=s；p->right->left=s；s->left=p；s->right=p->right； (D) s->left=p；s->right=p->right；p->right->left=s；p->right=s； 6．下列各种排序算法中平均时间复杂度为O(n2)是（）。 (A) 快速排序(B) 堆排序(C) 归并排序(D) 冒泡排序 7．设输入序列1、2、3、…、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（）。 (A) n-i (B) n-1-i (C) n+l -i (D) 不能确定 8．设散列表中有m个存储单元，散列函数H(key)= key%p，则p最好选择（）。 (A) 小于等于m的最大奇数(B) 小于等于m的最大素数 (C) 小于等于m的最大偶数(D) 小于等于m的最大合数 9．设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有（）个。 (A) 4 (B) 5 (C) 6 (D) 7 10.设完全无向图中有n个顶点，则该完全无向图中有（）条边。 (A) n(n-1)/2 (B) n(n-1) (C) n(n+1)/2 (D) (n-1)/2 11.设顺序表的长度为n，则顺序查找的平均比较次数为（）。 (A) n (B) n/2 (C) (n+1)/2 (D) (n-1)/2 12.设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24 的元素需要经过（）次比较。 (A) 1 (B) 2 (C) 3 (D) 4 13.设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查 找长度为（）。 (A) 6 (B) 11 (C) 5 (D) 6.5 14.设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，则下列属于该 有向图G的一种拓扑排序序列的是（）。 (A) 1，2，3，4 (B) 2，3，4，1 (C) 1，4，2，3 (D) 1，2，4，3 15.设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生 成的二叉排序树的深度为（）。 (A) 4 (B) 5 (C) 6 (D) 7 二、填空题(30分) 1．设指针p指向单链表中结点A，指针s指向被插入的结点X，则在结点A的前面插入结点X时的操作序列为： 1) s->next=___________；2) p->next=s；3) t=p->data； 4) p->data=___________；5) s->data=t； 2．设某棵完全二叉树中有100个结点，则该二叉树中有______________个叶子结点。3．设某顺序循环队列中有m个元素，且规定队头指针F指向队头元素的前一个位置，队尾指针R指向队尾元素的当前位置，则该循环队列中最多存储_______队列元素。4．对一组初始关键字序列（40，50，95，20，15，70，60，45，10）进行冒泡排序，则第一趟需要进行相邻记录的比较的次数为__________，在整个排序过程中最多需要进行__________趟排序才可以完成。 5．在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑应最好选择_________排序，如果从节省存储空间的角度来考虑则最好选择________排序。6．设一组初始记录关键字序列为(20，12，42，31，18，14，28)，则根据这些记录关键字构造的二叉排序树的平均查找长度是_______________________________。 7．设一棵二叉树的中序遍历序列为BDCA，后序遍历序列为DBAC，则这棵二叉树的前序序列为____________________。 8．设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为7、19、2、6、 32、3、21、10，根据这些频率作为权值构造哈夫曼树，则这棵哈夫曼树的高度为 ________________。 9．设一组记录关键字序列为(80，70，33，65，24，56，48)，则用 筛选法建成的初始堆为_______________________。 10．设无向图G（如右图所示），则其最小生成树上所有边的权值之 和为_________________。 三、判断题(20分) 1．有向图的邻接表和逆邻接表中表结点的个数不一定相等。( ) 2．对链表进行插入和删除操作时不必移动链表中结点。( ) 3．子串“ABC”在主串“AABCABCD”中的位置为2。( ) 4．若一个叶子结点是某二叉树的中序遍历序列的最后一个结点，则它必是该二叉树的先序遍历序列中的最后一个结点。( ) 5．希尔排序算法的时间复杂度为O(n2)。( ) 6．用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。( ) 7．中序遍历一棵二叉排序树可以得到一个有序的序列。( ) 8．入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。( ) 9．顺序表查找指的是在顺序存储结构上进行查找。（） 10．堆是完全二叉树，完全二叉树不一定是堆。（） 五、算法设计题(20分) 1．设计计算二叉树中所有结点值之和的算法。2．设计将所有奇数移到所有偶数之前的算法。3．设计判断单链表中元素是否是递增的算法。 数据结构试卷（九）参考答案 一、选择题 1．A 2．A 3．A 4．C 5．D 6．D 7．C 8．B 9．C 10．A 11．C 12．C 13．D 14．A 15．A 二、填空题 1.p->next，s->data 2.50 3.m-1 4.6，8 5.快速，堆 6.19/7 7.CBDA 8. 6 9.(24，65，33，80，70，56，48) 10.8 三、判断题 1．错2．对3．对4．对5．错 6．错7．对8．对9．错10．对 四、算法设计题 1．设计计算二叉树中所有结点值之和的算法。 void sum(bitree *bt,int &s) { if(bt!=0) {s=s+bt->data; sum(bt->lchild,s); sum(bt->rchild,s);} } 2．设计将所有奇数移到所有偶数之前的算法。 void quickpass(int r[], int s, int t) { int i=s,j=t,x=r[s]; while(i { while (i while (i } r[i]=x; } 3．设计判断单链表中元素是否是递增的算法。 int isriselk(lklist *head) { if(head==0||head->next==0) return(1);else for(q=head,p=head->next; p!=0; q=p,p=p->next)if(q->data>p->data) return(0); return(1); } 一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价,不包括如下（B ）方面的内容。 Ａ.健壮性和可读性Ｂ．并行性C。正确性Ｄ．时空复杂度 2.2．在带有头结点的单链表ＨL中,要向表头插入一个由指针p指向 的结点，则执行（A ). Ａ. p－〉ｎｅxt=HL->nexｔ; ＨL-〉nexｔ=p; B． p-〉next=HL；ＨL=p； Ｃ。p-＞ｎext=HＬ； p＝HL；Ｄ. HL=p; ｐ－〉next＝ＨL； 3.3．对线性表,在下列哪种情况下应当采用链表表示？( B ） Ａ.经常需要随机地存取元素 B。经常需要进行插入和删除操作 C。表中元素需要占据一片连续的存储空间D．表中元素的个数不变 4. 4.一个栈的输入序列为１ 2 3，则下列序列中不可能是栈的输出序 列的是( C ） A. 2 3 1 ??? B. ３ 2 1 C。 3 １ 2 ??? D. 1 ２３ 5. 5.AＯV网是一种（D ）。 A．有向图Ｂ．无向图Ｃ．无向无环图D．有向无环图 6.6。采用开放定址法处理散列表的冲突时,其平均查找长度（Ｂ)。 A．低于链接法处理冲突B．高于链接法处理冲突Ｃ.与链接法处理冲突相同 D。高于二分查找 7.7。若需要利用形参直接访问实参时，应将形参变量说明为（D ) 参数. Ａ。值Ｂ。函数 C.指针 D。引用 8.８．在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结 点都具有相同的（ A )。 A。行号 B.列号 C．元素值 D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为( D )。 A。O（loｇ 2n) B．Ｏ（nlog 2 n） C。０（n) D.0 （n2） 10.10.从二叉搜索树中查找一个元素时,其时间复杂度大致为( C ). Ａ．O(n） B. Ｏ(1） C。 O（log 2 n） D. O(n2)二、运算题（每题 6 分，共２４分） 数据结构模拟试卷（一） 一、选择题（每题2分，20题，共40分） 1. 数组A[1..5,1..6]的每个元素占5个单元，将其按行优先顺序存储在起始地址为1000的连续的内存单元中，则元素A[5,5]的地址为（）。 A．1140 B．1145 C．1120 D．1125 2. 下面的序列中，（）是堆。 A．1,510,6,7,8,9,2 B．1,2,8,4,3,9,10,5 C．9,8,7,6,4,8,2,1 D．9,8,7,6,5,4,3,7 3. 二叉树上结点的左子树深度减去其右子树深度称为该结点的平衡因子。平衡二叉树中任意结点的平衡因子只能是（）。 A．0 B．0,1 C．-1,0,1 D．1 4. 栈和队列的共同特点是： A．都是先进先出B．都是先进后出 C．只允许在端点处插入和删除元素D．没有共同点 5. 若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的出栈的不同排列个数为( ) A．4 B．5 C．6 D．7 6. 关键路径是AOE网中的______ 。 A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最短的回路 D．活动的最早开始时间与最迟发生时间相等 7. 已知数据元素为( 32 ，75 ，46 ，19 ，26，56 ，93 ，66 )，按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为（）。 A．4 B．5 C．7 D．6 8. 下列说法不正确的是______。 A．图的遍历是从给定的源点出发，每一个顶点仅被访问一次 B．遍历的基本算法有两种：深度遍历和广度遍历 C．图的深度遍历不适用于有向图 D．图的深度遍历是一个递归过程 9. 单循环链表的主要优点是（）。 A．从表中任一结点出发都能扫描到整个链表 B．不再需要头指针了 C．在进行插入、删除操作时，能更好地保证链表不断开 D．已知某个结点的位置后，能够容易找到它的直接前趋 10. 已知一棵树的前序遍历是”GDAFEMHZ”，而中序遍历是”ADEFGHMZ”，求后序遍历？A．ADEFGHMZ B．DAEFHZMG C．AEFDHZMG D．AFEDHMZG 11. 一个包含n个节点的四叉树，每个节点都有四个指向孩子节点的指针，这4n个指针中有多少个空指针？ A．2n+1 B．3n-1 C．3n D．3n+1 12. 和顺序栈相比,链栈有一个比较明显的优势是() A．通常不会出现栈满的情况 数据结构试卷（一） 一、选择题（20分） 1．组成数据的基本单位是（ 1.C ）。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（ C ）。 (A) 线性结构(B) 树型结构(C) 图型结构(D) 集合 3．数组的逻辑结构不同于下列（D）的逻辑结构。 (A) 线性表(B) 栈(C) 队列(D) 树 4．二叉树中第i(i≥1)层上的结点数最多有（C）个。 (A) 2i (B) 2i(C) 2i-1(D) 2i-1 5．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（.A ）。 (A) p->next=p->next->next (B) p=p->next (C) p=p->next->next (D) p->next=p 6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（.C ）。 (A) 6 (B) 4 (C) 3 (D) 2 7．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（C ）。 (A) 100 (B) 40 (C) 55 (D) 80 8．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（8.B (A) 3 (B) 4 (C) 5 (D) 1 9．根据二叉树的定义可知二叉树共有（B）种不同的形态。 (A) 4 (B) 5 (C) 6 (D) 7 10.设有以下四种排序方法，则（B ）的空间复杂度最大。 (A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序 二、填空题(30分) 1.设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元 素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =____________;。 2.设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为___________， 在链式存储结构上实现顺序查找的平均时间复杂度为___________。 3.设一棵二叉树中有n个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有________个指 针域，__________个空指针域。 4.设指针变量p指向单链表中结点A，指针变量s指向被插入的结点B，则在结点A的后面插入结点 B的操作序列为______________________________________。 5.设无向图G中有n个顶点和e条边，则其对应的邻接表中有_________个表头结点和_________个表 结点。 6.设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有______关系。 7.设一棵二叉树的前序遍历序列和中序遍历序列均为ABC，则该二叉树的后序遍历序列为__________。 8.设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编 号为8的双亲结点的编号是___________，编号为8的左孩子结点的编号是_____________。 9.下列程序段的功能实现子串t在主串s中位置的算法，要求在下划线处填上正确语句。 int index(char s[ ], char t[ ]) { i=j=0; while(i 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 单项选择题1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 、 1. 对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为 (c )。 (A)、正确性但).可行性(C).健壮性 2 ?设S为C语言的语句,计算机执行下面算法时， for(i=n-1 ; i>=0; i--) for(j=0 ; jvi; j++) (A)、n2(B). O(nlgn) 3?折半查找法适用于( a (D). 输入性 算法的时间复杂度为(d S； (C). O(n) (D). )。 O(n2) (A)、有序顺序表(B)、有序单链表 (C)、有序顺序表和有序单链表都可以 4 .顺序存储结构的优势是( d )。 (A)、利于插入操作(B)、利于删除操作 (C)、利于顺序访问(D)、利于随机访问 5. 深度为k的完全二叉树，其叶子结点必在第 (A)、k-1 ( B)、k (C)、k-1 和 6. 具有60个结点的二叉树，其叶子结点有 (A)、11 ( B)、13 ( C)、48 (D)、无限制 c )层上。 (D)、1 至 k 12个，则度过1 (D)、37 k 的结点数为( 7 .图的Depth-First Search(DFS) 遍历思想实际上是二叉树( 法的推广。 (A)、先序(B)、中序(C)、后序(D)、层序 8.在下列链队列Q中，元素a出队的操作序列为( a )遍历方 front (A )、 (B )、 (C)、 (D )、p=Q.front->next; p->next= Q.front->next; p=Q.front->next; Q.front->next=p->next; p=Q.rear->next; p->next= Q.rear->next; p=Q->next; Q->next=p->next; 9. Huffman树的带权路径长度WPL等于( (A)、除根结点之外的所有结点权值之和(C)、各叶子结点的带权路径长度之和(B) 、 ) 所有结点权值之和 根结点的值 b ■ 数据结构模拟试题一 一、判断题（每小题1 分，共15分） 1.计算机程序处理的对象可分为数据和非数据两大类。 2.全体自然数按大小关系排成的序列是一个线性表。 3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。 4.顺序栈是一种规定了存储方法的栈。 5.树形结构中的每个结点都有一个前驱。 6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。 7.若某顶点是有向图的根，则该顶点的入度一定是零。 8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。 9.用一维数组表示矩阵可以节省存储空间。 10.广义表的长度与广义表中含有多少个原子元素有关。 11.分块查找的效率与线性表被分成多少块有关。 12.散列表的负载因子等于存入散列表中的结点个数。 13.在起泡排序过程中，某些元素可能会向相反的方向移动。 14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。 15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。 二、填空题（每空1分，共15分） 1.顺序表是一种_____________线性表。 2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。 3.栈和队列的区别在于________的不同。 4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。 5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域 为空的结点。 6.n个顶点的有根有向图中至少有___条边，至多有___条边。 7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。 8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是 _____。 9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。 10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。 三、选择题（每题2分，共30分） 1.计算机所处理的数据一般具有某种内在联系性，这是指________。 A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系 C．元素内部具有某种结构D．数据项和数据项之间存在某种关系 2. 假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4 。若把新插入元素存入R[6]，则________。 A．会产生运行错误B．R[1]~R[6]不构成一个顺序表 C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率 D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦 3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后一个结点时，_________。A．P所指结点指针字段的值为空B．P的值与H的值相等 C．P所指结点的地址与H的值相等D．P所指结点指针字段的值与H的值相等 4. 栈的定义不涉及数据的__________。 A．逻辑结构B．存储结构C．运算D．逻辑结构和存储结构 5. 设5个元素进栈的顺序是1,2,3,4,5，则出栈的顺序有可能是___________。 A．2,4,1,3,5 B．3,4,1,5,2 C．3,2,4,1,5 D．4,1,3,2,5 6. 若某棵二叉树结点的前序序列和中序序列相同，则该二叉树_________。 A．只有一个结点B．每个结点都没有左孩子C．每个结点都没有右孩子D．不存在 7.对于一棵具有n个结点，度为3的树来说，____________。 A．树的高度至多是n-3 B．树的高度至多是n-2 C．树的最低高度是┏log3(n+1)┓ D．至少在某一层上正好有3个结点 8．n个顶点的有向图如果可以进行拓扑排序，则可以断定该有向图__________。 A．含n个强连通分量B．有唯一的入度为0的顶点C．有多个出度为0的顶点 D．是一个有根有向图 9. 特殊矩阵用行优先顺序表表示，_____________ A．简化了矩阵元素之间的逻辑关系B．便于按行处理矩阵元素 少年易学老难成，一寸光阴不可轻- 百度文库 《数据结构》 一、单项选择题（本大题共10小题，每小题3分，共30分） 1、若进栈的序列为1，2，3，4，则不可能得到的出栈序列是（）。 A. 3,2,1,4 B. 3,2,4,1 C. 4,2,3,1 D. 2,3,4,1 2、深度为k的完全二叉树所含叶结点的个数最多为（），设根结点在第1层上。 A. 2k B. 2k-1 C. k D. 2k-1 3、衡量查找算法效率的主要标准是（）。 A. 元素个数 B. 所需的存储量 C. 平均查找长度 D. 算法难易程度 4、与线性表的顺序存储不相符的特性是（）。 A. 插入和删除操作灵活 B. 需要连续的存储空间 C. 便于随机访问 D. 存储密度大 5、若进队序列为1，2，3，则出队序列是（）。 A. 3,2,1 B. 1,2,3 C. 1,3,2 D. 3,1,2 6、不带头结点的单链表L为空的判定条件是（）。 A. L==NULL B. L->next==NULL C. L->next==L D. L!=NULL 7、union(A,B,C)表示求集合A和B的并集C。若A={a,b,c},B={c,d},则union(A,B,C)运算后C=（）。 A．{a,b,c,d} B．{a,b,c} C．{a,b} D．{c,d} 8、数组A中，每个元素的长度为3个存储单元，行下标i从1到5，列下标j从1到6，从首地址SA开始连续存放在存储器内，存放该数组至少需要的存储单元数是（）。 A. 90 B. 70 C. 50 D. 30 9、遍历一棵具有n个结点的二叉树，在先序序列、中序序列和后序序列中所有叶子结点的相对次序（）。 A. 都不相同 B. 完全相同 C. 先序和中序相同 D. 中序和后序相同 10、用给定的哈夫曼编码来压缩数据文件，其压缩效率主要取决于（）。 A. 文件长度 B. 平均码长 C. 被压缩文件的特征 D. 以上都不是 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、当利用大小为N的数组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时，首先应执行（）语句修改top指针。 A. top++ B. top-- C. top=0 D. top=N-1 7、在一个带头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（）个指针域的值。 A. 2 B. 3 C. 4 D. 5 8、利用3,6,8,12,5,7这六个值作为叶子结点的权，生成一棵哈夫曼树，该树的深度为（）。 A. 3 B. 4 数据结构试卷带答案 问题说明 部分题目或答案有问题，现将已经发现的公布如下，同学在作这些模拟题的时候应着重做题方法的理解，遇到问题以教材或课件为准，不确定的地方可找同学商量或问我 （1）试卷1第一套填空题第1题，试卷1第2套选择题第3题关于循环队列队头指针和队尾指针的约定与教材不一致，以教材或课件为准，实际上front指向的是队头元素，rear指向当前尚未被占用的第一个队列空间，队慢或队空的判定条件及入队/出队等操作具体可参考课件或教材 （2）试卷1第一套应用题第5题，不声明邻接点顺序时默认编号最小的邻接点为第一邻接点，该图的深度优先遍历序列为123465,答案错。此外，当给定邻接表时则邻接点顺序按照邻接表中的前后顺序确定，如试卷1第二套填空题第8题 （3）试卷1第五套应用题第4题，两种方法处理冲突的方法下所求ASL值相等都为7/6 （4）试卷1第五套填空题第8题答案给出的是小顶堆需满足的条件，大顶堆满足ki>=k2i p->rlink->llink=p->llink;此外，注意课堂中讲的指针名和操作方法 （12）第4套填空题第6题答案错，设哈夫曼树中共有99个结点，则该树中有____50_____个叶子结点；若采用二叉链表作为存储结构，则该树中有__100___个空指针域。 （13）第5套选择第8题答案应为A:设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为(A) abedfc (14)第5套应用题第3题题目未指明查找方法，没法作 （15）第6套选择第5题应选B，实际是任意结点至多只有一个孩子：设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是(B) 高度等于其结点数 （16）第7套填空1题问题本身错，设指针变量p指向双向链表中的结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为____s->left_____=p；s->right=p->right；___p->right_______=s；s->right->left=s；（设结点中的两个指针域分别为left和right）。（17）第8套填空题第8题答案错 （18）第7套选择第3题题目错，应以60为基准关键字，答案为C．设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字60为基准而得到的一趟快速排序结果是（）。 (C) 42，40，55，60，80，85 （17）第6套填空9题．快速排序算法的空间复杂度平均情况下为_O(logn)_，最坏的情况下为_O(n)_。(18)第9套填空第3题，题目说循环队列有m个元素实际指循环队列总长为m，此外，该题关于队头和队尾指针的约定不同于教材 （19）第9套填空第4题答案错，9个元素冒泡排序，第一趟比较次数为8，最多8趟 《数据结构》试题参考答案 （开卷） （电信系本科2001级 2002年12月） 一、回答下列问题 (每题4分，共36分) 1. 某完全二叉树共有15381个结点，请问其树叶有多少个？ 答：n2=?n/2?=?15381/2?=7691(个) 2. 假设有二维数组A 7×9，每个元素用相邻的6个字节存储，存储器按字节编址。已知A 的起始存储位置（基地址）为1000，末尾元素A[6][8]的第一个字节地址为多少？若按列存储时，元素A[4][7]的第一个字节地址为多少？ 答：① 末尾元素A[6][8]的第一个字节地址＝1000＋（7行×9列—1）×6B ＝1000＋62×6=1372 ②按列存储时，元素A[4][7]的第一个字节地址＝1000＋（7列×7行＋4）×6B ＝1000＋53×6=1318 3. 在KMP 算法中，已知模式串为ADABBADADA ，请写出模式串的next[j]函数值。 答：根据 0 当j ＝1时 next[ j ]＝ max { k |1 一、单项选择题（在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。每小题2分，共40分） 1、串的长度是（）。 A、串中不同字母的个数 B、串中不同字符的个数 C、串中所含字符的个数，且大于0 D、串中所含字符的个数 2、若用数组S[1..n]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（）。 A、S1的栈底位置为0，S2的栈底位置为n+1 B、S1的栈底位置为0，S2的栈底位置为n/2 C、S1的栈底位置为1，S2的栈底位置为n D、S1的栈底位置为1，S2的栈底位置为n/2 3、队列操作的原则是（）。 A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除 4、有64个结点的完全二叉树的深度为（）（根的层次为1）。 A、8 B、7 C、6 D、5 5、在有n个结点的二叉链表中，值为非空的链域的个数为（）。 A、n-1 B、2n-1 C、n+1 D、2n+1 6、带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中（）。 A、第i行非∞的元素之和 B、第i列非∞的元素之和 C、第i行非∞且非0的元素个数 D、第i列非∞且非0的元素个数 7、在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。 A、0(n) B、0(log2n) C、0(nolg2n) D、0(n2) 8、若表R在排序前已按键值递增顺序排列，则（）算法的比较次数最少。 A、直接插入排序 B、快速排序 C、归并排序 D、选择排序 9、下列排序算法中，（）排序在某趟结束后不一定选出一个元素放到其最终的位置上。 A、选择 B、冒泡 C、归并 D、堆 第一章概论 一、选择题 1、研究数据结构就是研究（Ｄ）。 Ａ. 数据的逻辑结构?B。数据的存储结构 C。数据的逻辑结构和存储结构?D．数据的逻辑结构、存储结构及其基本操作(研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作) 2、算法分析的两个主要方面是（Ａ）。 A．空间复杂度和时间复杂度???B。正确性和简单性 C。可读性和文档性D．数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。(线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素,有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继)（链表、栈、队列、数组、串） A. 图Ｂ. 树??C．广义表(线性表的推广) D．栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、（ B ）等5个特性。 Ａ．可执行性、可移植性和可扩充性? B. 可执行性、有穷性和确定性 C。确定性、有穷性和稳定性??? D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C ）。 for(i=0；i 一．是非题 （正确的打“√”，错误的打“×”。） 1. 数据结构可用三元式表示（D，S，P）。其中：D是数据对象，S是D上的关系， P是对D的基本操作集。× 2. 线性表的链式存储结构具有可直接存取表中任一元素的优点。× 3. 字符串是数据对象特定的线性表。 4. 二叉树是一棵结点的度最大为二的树。× 5．邻接多重表可以用以表示无向图，也可用以表示有向图。× 6．可从任意有向图中得到关于所有顶点的拓扑次序。× 7．一棵无向连通图的生成树是其极大的连通子图。× 8．二叉排序树的查找长度至多为log2ｎ。× 9．对于一棵m阶的B-树.树中每个结点至多有m 个关键字。除根之外的所有非终端结点至少有┌m/2┐个关键字。× 10．对于目前所知的排序方法，快速排序具有最好的平均性能。 11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。× 12. 二维数组是其数据元素为线性表的线性表。 13. 连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。× 14. 折半查找不适用于有序链表的查找。 15. 完全二叉树必定是平衡二叉树。 16. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。 17. 队列是与线性表完全不同的一种数据结构。× 18. 平均查找长度与记录的查找概率有关。 19. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。× 20. 算法的时间复杂性越好，可读性就越差；反之，算法的可读性越好，则时间复杂性就越差。× 二．选择题 1. 若对编号为1，2，3的列车车厢依次通过扳道栈进行调度，不能得到 ( e ) 的序列。 a:1,2,3 b:1,3,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,1 2. 递归程序可借助于( b )转化为非递归程序。 a:线性表 b: 栈 c:队列 d:数组 3. 在下列数据结构中( c )具有先进先出（FIFO）特性， ( b )具有先进后出(FILO）特性。 a:线性表 b:栈 c:队列 d:广义表 4. 对字符串s=’data-structure’ 执行操作replace(s,substring(s,6,8),’bas’) 数据结构模拟卷(含答案)经典习题 练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位10. 下列图示的顺序存储结构表示的二叉树是( ) 《数据结构》试卷B 一、填空题（每空1分，共15分） 1. 向量、栈和队列都是结构，可以在向量的位置插入和删除元素；对于栈 只能在插入和删除元素；对于队列只能在插入和删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为。不允许插入和删除 运算的一端称为。 3. 数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间 的和运算等的学科。 4. 在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 5. 在具有n个单元的循环队列中，队满时共有个元素。 6. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查 找成功的结点数为；比较四次查找成功的结点数为；平均查找长度为。 二、判断正误（判断下列概念的正确性，并作出简要的说明。）（每小题1分，共10分） （）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（）2. 在表结构中最常用的是线性表，栈和队列不太常用。 （）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。（）5.线性表的逻辑顺序与存储顺序总是一致的 （）6. 栈和队列是一种非线性数据结构。 （）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 （）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 1 6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位 10. 下列图示的顺序存储结构表示的二叉树是( ) 2 数据结构试题（含答案） 1．数据逻辑结构包括线性结构、树形结构和图状结构三种类型，树形结构和图状结构合称非线性结构 2．数据的逻辑结构分为集合、线性结构、树形结构和图状结构 4种。 3．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有 1 个后续结点。 4．线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 5．在树形结构中，树根结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；叶子结点没． 6．数据结构的基本存储方法是顺序、链式、索引和散列存储。有后续结点，其余每个结点的后续结点可以任意多个。 7．衡量一个算法的优劣主要考虑正确性、可读性、健壮性和时间复杂度与空间复杂度。8．评估一个算法的优劣，通常从时间复杂度和空间复杂度两个方面考察。 9．算法的5个重要特性是有穷性、确定性、可行性、输入和输出。 10．在单链表中，要删除某一指定的结点，必须找到该结点的前驱结点。 11．在单链表中，要删除某一指定的结点，必须找到该结点的前驱结点。 12．在双链表中，每个结点有两个指针域，一个指向前驱结点，另一个指向后继结点。13．在顺序表中插入或删除一个数据元素，需要平均移动 n 个数据元素，移动数据元素的个数与位置有关 14．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表的元素是，应采用顺序存储结构 15．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成单链表和双链表。 16．顺序存储结构是通过下标表示元素之间的关系的；链式存储结构是通过指针表示元素之间的关系的 17．带头结点的循环链表L中只有一个元素结点的条件是 L->next->next=L 18．栈是限定仅在表尾进行插入或删除操作的线性表，其运算遵循后进先出的原则。19．空串是零个字符的串，其长度等于零。空白串是由一个或多个空格字符组成的串，其长度等于其包含的空格个数。 20．组成串的数据元素只能是单个字符。 21．一个子串”str”在主串”datastructure”中的位置是 5 。 22．字符串中任意个连续字符构成的部分称为该串的子串。 23．二维数组M的每个元素是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要 540个字节；M的第8列和第5行共占108个字节24．稀疏矩阵一般的压缩存储方法有两种，即三元组表和十字链表。 25．广义表（（a），（（b），c），（（（d））））的长度是 3 ，深度是 4 。 26．在一棵二叉树中，度为零的结点的个数为n0，度为2 的结点的个数为n2，则有n0＝ n2+1 。 27．在有n个结点的二叉链表中，空链域的个数为__n+1__。 28．一棵有n个叶子结点的哈夫曼树共有__2n-1_个结点 29．深度为5的二叉树至多有 31 个结点。 30．若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点个数为69 。 模拟试卷一 一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点， 则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成 ( )个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 A． 11 B.35 C. 19 D. 53 图一 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建 堆的结果?( ) 一、判断题： 1、线性表的逻辑顺序与物理顺序总是一致的。( ) 2、线性表的顺序存储表示优于链式存储表示。( ) 3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。( ) 4、二维数组是其数组元素为线性表的线性表。( ) 5、每种数据结构都应具备三种基本运算：插入、删除和搜索。( ) 6、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个 方面。( ) 7、线性表中的每个结点最多只有一个前驱和一个后继。（） 8、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。（） 9、栈和队列逻辑上都是线性表。（） 10、单链表从任何一个结点出发，都能访问到所有结点（） 11、删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。（） 12、快速排序是排序算法中最快的一种。（） 13、多维数组是向量的推广。（） 14、一般树和二叉树的结点数目都可以为0。（） 15、直接选择排序是一种不稳定的排序方法。（） 16、98、对一个堆按层次遍历，不一定能得到一个有序序列。（） 17、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。（） 18、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。（） 19、堆栈在数据中的存储原则是先进先出。（） 20、队列在数据中的存储原则是后进先出。（） 21、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。（） 22、哈夫曼树一定是满二叉树。（） 23、程序是用计算机语言表述的算法。（） 24、线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。（） 25、用一组地址连续的存储单元存放的元素一定构成线性表。（） 26、堆栈、队列和数组的逻辑结构都是线性表结构。（） 27、给定一组权值，可以唯一构造出一棵哈夫曼树。（） 28、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。（） 《数据结构》试卷及答案 1．算法分析的目的是( )。 A.找出数据结构的合理性 B.研究算法中输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2．（）是具有相同特性数据元素的集合，是数据的子集。 A.数据符号 B.数据对象 C.数据 D.数据结构 3．用链表表示线性表的优点是( )。 A.便于随机存取 B.花费的存储空间比顺序表少 C.便于插入与删除 D.数据元素的物理顺序与逻辑顺序相同 4．输入序列为（A,B,C,D）不可能的输出有（）。 A.(A,B,C,D) B. (D,C,B,A) C. (A,C,D,B) D . (C,A,B,D) 5．在数组表示的循环队列中，front、rear分别为队列的头、尾指针，maxSize为数组的最大长度，队满的条件是( )。 A. front=maxSize B. (rear+1)%maxSize=front C. rear=maxSize D. rear=front 6．设有串t='I am a good student '，那么Substr(t,6,6)=（）。 A. student B. a good s C. good D. a good 7．设有一个对称矩阵A，采用压缩存储方式，以行序为主序存储a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则a85地址为（）。 A.23 B.33 C.18 D. 40 8．已知广义表LS=(A,(B,C,D),E)运用head和tail函数，取出LS中原子b的运算（）。 A. Gethead(Gethead(LS)) B. Gettail(Gethead(LS)) C. Gethead(Gethead(Gettail(LS))) D. Gethead(Gettail(LS)) 9．若已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为( ) A. CDBGFEA B. CDBFGEA C. CDBAGFE D. BCDAGFE 10．下列存储形式中，( ) 不是树的存储形式。 A.双亲表示法 B.左子女右兄弟表示法 C.广义表表示法 D.顺序表示法 11．对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是( )。 A.直接选择排序 B.直接插入排序 C.快速排序 D.起泡排序 12．采用折半查找方法进行查找，数据文件应为（），且限于（）。数据结构试题及答案10套
数据结构模拟试卷(一)
数据结构试卷带答案
数据结构期末考试试题及答案
数据结构模拟试题及答案
大工数据结构课程考试模拟试卷a
数据结构试卷带答案
数据结构试卷和答案
数据结构模拟试题1
数据结构试题及答案
数据结构试题(含答案)
数据结构模拟卷(含答案)经典习题培训讲学
数据结构试卷B卷(含答案)
数据结构模拟卷(含答案)经典习题
数据结构试题(含答案)
《数据结构》模拟试卷一及答案
数据结构试题及答案
数据结构试卷及答案压缩版