《2022年考研计算机数据结构试题及答案 .pdf》由会员分享，可在线阅读，更多相关《2022年考研计算机数据结构试题及答案 .pdf（23页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2015 年考研必备资料2015年考研计算机数据结构试题及答案目录2015 年考研计算机数据结构试题及答案（1） . 2 2015 年考研计算机数据结构试题（1） . 2 2015 年考研计算机数据结构试题答案（1） . 5 2015 年考研计算机数据结构试题及答案（2） . 6 2015 年考研计算机数据结构试题（2） . 6 2015 年考研计算机数据结构试题答案（2） . 9 2015 年考研计算机数据结构试题及答案（3） . 11 2015 年考研计算机数据结构试题（3） . 11 2015 年考研计算机数据结构试题答案（3） . 13 2015 年考研计算机数据结构试题及答案（4）
2、. 15 2015 年考研计算机数据结构试题（4） . 15 2015 年考研计算机数据结构试题答案（4） . 17 2015 年考研计算机数据结构试题及答案（5） . 19 2015 年考研计算机数据结构试题（5） . 19 2015 年考研计算机数据结构试题答案（5） . 21 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 23 页 - - - - - - - - - 第 2 页 共 23 页2015 年考研计算机数据结构试题及答案（1）2015年考研计算机数据结构
3、试题（1）一、选择题 (24 分)1. 下列程序段的时间复杂度为( ) 。i=0 ，s=0; while (s (A) O(n1/2) (B) O(n1/3) (C) O(n) (D) O(n2) 2. 设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列( ) 存储方式最节省运算时间。(A) 单向链表 (B) 单向循环链表(C) 双向链表 (D) 双向循环链表3. 设指针 q 指向单链表中结点A，指针 p 指向单链表中结点A的后继结点 B，指针 s 指向被插入的结点 X，则在结点 A和结点 B插入结点 X的操作序列为 ( ) 。(A) s-next=p-next;p-next=-s
4、; (B) q-next=s; s-next=p; (C) p-next=s-next;s-next=p; (D) p-next=s;s-next=q; 4. 设输入序列为 1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为( ) 。(A) 5 ，3，4，6，1，2 (B) 3 ，2，5，6，4，1 (C) 3 ，1，2，5，4，6 (D) 1 ，5，4，6，2，3 5. 设有一个 10 阶的下三角矩阵 A(包括对角线 ) ，按照从上到下、从左到右的顺序存储到连续的 55 个存储单元中，每个数组元素占1 个字节的存储空间，则A54地址与 A00的地址之差为 ( ) 。(A) 10 (
5、B) 19 (C) 28 (D) 55 6. 设一棵 m叉树中有 N1个度数为 1 的结点， N2个度数为 2 的结点， , ，Nm个度数为m的结点，则该树中共有 ( ) 个叶子结点。(A) (B) (C) (D) 7. 二叉排序树中左子树上所有结点的值均( ) 根结点的值。(A) (C) = (D) != 8. 设一组权值集合W=(15 ，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为( ) 。(A) 129 (B) 219 (C) 189 (D) 229 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - -
6、- - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 23 页 - - - - - - - - - 第 3 页 共 23 页9. 设有 n个关键字具有相同的Hash函数值， 则用线性探测法把这n个关键字映射到 HASH表中需要做 ( ) 次线性探测。(A) n2 (B) n(n+1) (C) n(n+1)/2 (D) n(n-1)/2 10. 设某棵二叉树中只有度数为0 和度数为 2 的结点且度数为 0 的结点数为 n，则这棵二叉中共有 ( ) 个结点。(A) 2n (B) n+l (C) 2n-1 (D) 2n+l 11. 设一组初始记录关键字的长度为
7、8，则最多经过 ( ) 趟插入排序可以得到有序序列。(A) 6 (B) 7 (C) 8 (D) 9 12. 设一组初始记录关键字序列为(Q，H，C ，Y，P，A，M ，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是( ) 。(A) F ，H ，C ，D，P，A，M ，Q ，R ，S，Y，X (B) P ，A，C ，S，Q ，D ，F，X，R ，H ，M ，Y (C) A ，D ，C ，R，F，Q ，M ，S，Y，P，H ，X (D) H ，C ，Q ，P，A，M ，S，R ，D ，F，X，Y 二、填空题 (48 分，其中最后两小题各6 分)1. 1. 设需要对 5 个不同的记
8、录关键字进行排序，则至少需要比较_ 次，至多需要比较 _次。2. 2. 快速排序算法的平均时间复杂度为_ ，直接插入排序算法的平均时间复杂度为 _。3. 3. 设二叉排序树的高度为h， 则在该树中查找关键字key 最多需要比较 _次。4. 4. 设在长度为 20 的有序表中进行二分查找，则比较一次查找成功的结点数有_个，比较两次查找成功有结点数有_个。5. 5. 设一棵 m叉树脂的结点数为n， 用多重链表表示其存储结构， 则该树中有 _个空指针域。6. 6. 设指针变量 p 指向单链表中结点A，则删除结点 A的语句序列为：q=p-next;p-data=q-data;p-next=_;feee
9、(q); 7. 7. 数据结构从逻辑上划分为三种基本类型：_ 、_和_ 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 23 页 - - - - - - - - - 第 4 页 共 23 页8. 8. 设无向图 G中有 n 个顶点 e 条边，则用邻接矩阵作为图的存储结构进行深度优先或广度优先遍历时的时间复杂度为_;用邻接表作为图的存储结构进行深度优先或广度优先遍历的时间复杂度为_。9. 9. 设散列表的长度为8，散列函数 H(k)=k % 7 ，用线性探测法解决冲突，则
10、根据一组初始关键字序列 (8 ，15，16，22，30，32)构造出的散列表的平均查找长度是_。10. 10. 设一组初始关键字序列为(38，65，97，76，13，27，10)，则第 3 趟冒泡排序结束后的结果为 _ 。11. 11. 设一组初始关键字序列为(38，65，97，76，13，27，10)，则第 3 趟简单选择排序后的结果为 _ 。12. 12. 设有向图 G中的有向边的集合E=，则该图的一个拓扑序列为_ 。13. 13. 下面程序段的功能是建立二叉树的算法，请在下划线处填上正确的内容。typedef struct nodeint data;struct node *lchild
11、;_;bitree; void createbitree(bitree *&bt) scanf( “%c ”,&ch); if(ch=#) _;else bt=(bitree*)malloc(sizeof(bitree); bt-data=ch; _;createbitree(bt-rchild); 14. 14. 下面程序段的功能是利用从尾部插入的方法建立单链表的算法，请在下划线处填上正确的内容。typedef struct node int data; struct node *next; lklist; void lklistcreate(_ *&head ) for (i=1;i=n;
12、i+) p=(lklist *)malloc(sizeof(lklist);scanf(“%d ”,&(p-data);p-next=0; if(i=1)head=q=p;else q-next=p;_; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 23 页 - - - - - - - - - 第 5 页 共 23 页 三、算法设计题 (22 分)1. 1. 设计在链式存储结构上合并排序的算法。2. 2. 设计在二叉排序树上查找结点X的算法。3. 3. 设关键字序列
13、(k1 ，k2，, ， kn-1) 是堆，设计算法将关键字序列 (k1 ，k2， , ， kn-1 ，x) 调整为堆。2015 年考研计算机数据结构试题答案（1）一、选择题 1.A 2.D 3.B 4.B 5.B 6.D 7.A 8.D 9.D 10.C 11.B 12.D 二、填空题 1. 1. 4，10 2. 2. O(nlog2n)，O(n2) 3. 3. n 4. 4. 1，2 5. 5. n(m-1)+1 6. 6. q-next 7. 7. 线性结构，树型结构，图型结构 8. 8. O(n2)， O(n+e) 9. 9. 8/3 10. 10. (38，13，27，10，65，76
14、，97) 11. 11. (10，13，27，76，65，97，38) 12. 12. 124653 13. 13. struct node *rchild，bt=0，createbitree(bt-lchild) 14. 14. lklist，q=p 三、算法设计题 1. 1. 设计在链式存储结构上合并排序的算法。 void mergelklist(lklist *ha,lklist *hb,lklist *&hc) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 23
15、 页 - - - - - - - - - 第 6 页 共 23 页 lklist *s=hc=0; while(ha!=0 & hb!=0) if(ha-datadata)if(s=0) hc=s=ha; else s-next=ha; s=ha;ha=ha-next; else if(s=0) hc=s=hb; else s-next=hb; s=hb;hb=hb-next; if(ha=0) s-next=hb; else s-next=ha; 2. 2. 设计在二叉排序树上查找结点X的算法。 bitree *bstsearch1(bitree *t, int key) bitree *p
16、=t; while(p!=0) if (p-key=key) return(p);else if (p-keykey)p=p-lchild; else p=p-rchild; return(0); 3. 3. 设关键字序列 (k1 ，k2，, ， kn-1) 是堆，设计算法将关键字序列(k1 ，k2，, ， kn-1 ，x) 调整为堆。 void adjustheap(int r ,int n) int j=n,i=j/2,temp=rj-1; while (i=1) if (temp=ri-1)break; elserj-1=ri-1; j=i; i=i/2; rj-1=temp; 2015
17、 年考研计算机数据结构试题及答案（2）2015年考研计算机数据结构试题（2）一、选择题 (30 分)1. 下列程序段的时间复杂度为( ) 。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 个元素需要移动 ( ) 个元素。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 23 页 - - - - - - - - - 第 7 页 共 23 页(A)
18、 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的
19、操作序列为 ( ) 。(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)
20、冒泡排序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 的结点数有 (
21、 ) 个。(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 名师资料总结 - - -精品资料欢迎下载 - -
22、- - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 23 页 - - - - - - - - - 第 8 页 共 23 页13. 设顺序线性表的长度为30，分成 5 块，每块 6 个元素，如果采用分块查找，则其平均查找长度为 ( ) 。(A) 6 (B) 11 (C) 5 (D) 6.5 14. 设有向无环图 G中的有向边集合 E=，则下列属于该有向图 G的一种拓扑排序序列的是( ) 。(A) 1 ，2，3，4 (B) 2 ，3，4，1 (C) 1 ，4，2，3 (D) 1 ，2，4，3 15. 设有一组初始记录关键字序列为
23、(34，76，45，18，26，54，92)，则由这组记录关键字生成的二叉排序树的深度为( ) 。(A) 4 (B) 5 (C) 6 (D) 7 二、填空题 (30 分)1. 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. 2. 设某棵完全二叉树中有100 个结点，则该二叉树中有 _ 个叶子结点。3. 3. 设某顺序循环队列中有m个元素，且规定队头指针F指向队头元素的前一个位置，队尾指针 R指向队尾元
24、素的当前位置，则该循环队列中最多存储_队列元素。4. 4. 对一组初始关键字序列 (40，50，95，20，15，70，60，45，10)进行冒泡排序，则第一趟需要进行相邻记录的比较的次数为_ ，在整个排序过程中最多需要进行_ 趟排序才可以完成。5. 5. 在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑应最好选择_排序，如果从节省存储空间的角度来考虑则最好选择_排序。6. 6. 设一组初始记录关键字序列为(20，12，42，31，18，14，28)，则根据这些记录关键字构造的二叉排序树的平均查找长度是_ 。7. 7. 设一棵二叉树的中序遍历序列为BDCA ，后序遍历序列为 D
25、BAC ，则这棵二叉树的前序序列为 _ 。8. 8. 设用于通信的电文仅由8 个字母组成，字母在电文中出现的频率分别为7、19、2、6、32、3、21、10，根据这些频率作为权值构造哈夫曼树，则这棵哈夫曼树的高度为_ 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 23 页 - - - - - - - - - 第 9 页 共 23 页9. 9. 设一组记录关键字序列为(80，70，33，65，24，56，48)，则用筛选法建成的初始堆为 _ 。10. 10. 设无向图
26、G(如右图所示 ) ，则其最小生成树上所有边的权值之和为_ 。三、判断题 (20 分)1. 1. 有向图的邻接表和逆邻接表中表结点的个数不一定相等。( ) 2. 2. 对链表进行插入和删除操作时不必移动链表中结点。( ) 3. 3. 子串“ ABC ”在主串“ AABCABCD”中的位置为 2。( ) 4. 4. 若一个叶子结点是某二叉树的中序遍历序列的最后一个结点，则它必是该二叉树的先序遍历序列中的最后一个结点。( ) 5. 5. 希尔排序算法的时间复杂度为O(n2)。( ) 6. 6. 用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。 ( ) 7. 7.
27、 中序遍历一棵二叉排序树可以得到一个有序的序列。( ) 8. 8. 入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。( ) 9. 9. 顺序表查找指的是在顺序存储结构上进行查找。( ) 10.10. 堆是完全二叉树，完全二叉树不一定是堆。( ) 四、算法设计题 (20 分)1. 1. 设计计算二叉树中所有结点值之和的算法。2. 2. 设计将所有奇数移到所有偶数之前的算法。3. 3. 设计判断单链表中元素是否是递增的算法。2015 年考研计算机数据结构试题答案（2）一、选择题 1.A 2.A 3.A 4.C 5.D 6.D 7.C 8.B 9.C 10.A 11.C 12.C
28、13.D 14.A 15.A 二、填空题 1. 1. p-next，s-data 2. 2. 50 3. 3. m-1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 23 页 - - - - - - - - - 第 10 页 共 23 页 4. 4. 6，8 5. 5. 快速，堆 6. 6. 19/7 7. 7. CBDA 8. 8. 6 9. 9. (24，65，33，80，70，56，48) 10. 10. 8 三、判断题 1. 错 2. 对 3. 对 4. 对 5
29、. 错 6. 错 7. 对 8. 对 9. 错 10. 对四、算法设计题 1. 1. 设计计算二叉树中所有结点值之和的算法。 void sum(bitree *bt,int &s) if(bt!=0) s=s+bt-data; sum(bt-lchild,s); sum(bt-rchild,s); 2. 2. 设计将所有奇数移到所有偶数之前的算法。 void quickpass(int r, int s, int t) int i=s,j=t,x=rs; while(ij)/j) while (ij ri=rj;i=i+1;/p (i while (inext=0) return(1);els
30、e for(q=head,p=head-next; p!=0; q=p,p=p-next)if(q-datap-data) return(0); return(1); 2015 年考研计算机数据结构试题及答案（3）2015年考研计算机数据结构试题（3）一、选择题 (30 分) 1. 1. 字符串的长度是指 ( ) 。(A) 串中不同字符的个数 (B) 串中不同字母的个数(C) 串中所含字符的个数 (D) 串中不同数字的个数2. 2. 建立一个长度为n 的有序单链表的时间复杂度为( ) (A) O(n) (B) O(1) (C) O(n2) (D) O(log2n) 3. 3. 两个字符串相等的
31、充要条件是( ) 。(A) 两个字符串的长度相等 (B) 两个字符串中对应位置上的字符相等(C) 同时具备 (A) 和(B) 两个条件 (D) 以上答案都不对4. 4. 设某散列表的长度为100，散列函数 H(k)=k % P ，则 P通常情况下最好选择 ( ) 。(A) 99 (B) 97 (C) 91 (D) 93 5. 5. 在二叉排序树中插入一个关键字值的平均时间复杂度为( ) 。(A) O(n) (B) O(1og2n) (C) O(nlog2n) (D) O(n2) 6. 6. 设一个顺序有序表A1:14 中有 14 个元素，则采用二分法查找元素A4 的过程中比较元素的顺序为 (
32、) 。(A) A1，A2 ，A3 ，A4 (B) A1，A14 ，A7 ，A4 (C) A7，A3 ，A5 ，A4 (D) A7，A5 ，A3 ，A4 7. 7. 设一棵完全二叉树中有65 个结点，则该完全二叉树的深度为( ) 。(A) 8 (B) 7 (C) 6 (D) 5 8. 8. 设一棵三叉树中有2 个度数为 1 的结点， 2 个度数为 2 的结点， 2 个度数为 3 的结点，则该三叉链权中有 ( ) 个度数为 0 的结点。(A) 5 (B) 6 (C) 7 (D) 8 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名
33、师精心整理 - - - - - - - 第 11 页，共 23 页 - - - - - - - - - 第 12 页 共 23 页9. 9. 设无向图 G中的边的集合 E=(a，b)，(a，e)，(a ，c) ，(b，e) ，(e，d) ，(d，f) ，(f ，c) ，则从顶点 a 出发进行深度优先遍历可以得到的一种顶点序列为( ) 。(A) aedfcb (B) acfebd (C) aebcfd (D) aedfbc 10. 10. 队列是一种 ( ) 的线性表。(A) 先进先出 (B) 先进后出 (C) 只能插入 (D) 只能删除二、判断题 (20 分) 1. 1. 如果两个关键字的值不
34、等但哈希函数值相等，则称这两个关键字为同义词。( ) 2. 2. 设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n) 。( ) 3. 3. 分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。( ) 4. 4. 二维数组和多维数组均不是特殊的线性结构。( ) 5. 5. 向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。( ) 6. 6. 如果某个有向图的邻接表中第i 条单链表为空，则第i 个顶点的出度为零。 ( ) 7. 7. 非空的双向循环链表中任何结点的前驱指针均不为空。( ) 8. 8. 不
35、论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为 O(n)。( ) 9. 9. 图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问过。 ( ) 10. 10. 稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0 元素。( ) 三、填空题 (30 分) 1. 1. 设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则以 d=4 为增量的一趟希尔排序结束后的结果为_ 。2. 2. 下面程序段的功能是实现在二叉排序树中插入一个新结点，请在下划线处填上正确的内容。typedef struct nodeint dat
36、a;struct node *lchild;struct node *rchild;bitree; void bstinsert(bitree *&t,int k) if (t=0 ) _;t-data=k;t-lchild=t-rchild=0; else if (t-datak) bstinsert(t-lchild,k);else_; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 23 页 - - - - - - - - - 第 13 页 共 23 页 3. 3
37、. 设指针变量 p 指向单链表中结点A，指针变量 s 指向被插入的结点X，则在结点 A的后面插入结点 X需要执行的语句序列： s-next=p-next; _;。4. 4. 设指针变量 head指向双向链表中的头结点，指针变量p 指向双向链表中的第一个结点，则指针变量 p 和指针变量 head之间的关系是 p=_ 和 head=_(设结点中的两个指针域分别为llink和 rlink)。5. 5. 设某棵二叉树的中序遍历序列为ABCD ，后序遍历序列为 BADC ，则其前序遍历序列为_ 。6. 6. 完全二叉树中第5 层上最少有 _个结点，最多有 _个结点。7. 7. 设有向图中不存在有向边，则
38、其对应的邻接矩阵A中的数组元素 Aij的值等于_ 。8. 8. 设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则第 4 趟直接选择排序结束后的结果为_ 。9. 9. 设连通图 G中有 n 个顶点 e 条边，则对应的最小生成树上有_条边。10. 10. 设有一组初始记录关键字序列为(50，16，23，68，94，70，73)，则将它们调整成初始堆只需把16 与_相互交换即可。四、算法设计题 (20 分) 1. 1. 设计一个在链式存储结构上统计二叉树中结点个数的算法。2. 2. 设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。2015 年考研计算机数据结构试题
39、答案（3）一、选择题 1.C 2.C 3.C 4.B 5.B 6.C 7.B 8.C 9.A 10.A 二、判断题 1. 对 2. 错 3. 对 4. 错 5. 错 6. 对 7. 对 8. 对 9. 对 10. 对三、填空题 1. 1. (49，13，27，50，76，38，65，97) 2. 2. t=(bitree *)malloc(sizeof(bitree)，bstinsert(t-rchild,k) 3. 3. p-next=s 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - -
40、 第 13 页，共 23 页 - - - - - - - - - 第 14 页 共 23 页 4. 4. head-rlink，p-llink 5. 5. CABD 6. 6. 1，16 7. 7. 0 8. 8. (13，27，38，50，76，49，65，97) 9. 9. n-1 10. 10. 50 四、算法设计题 1. 1. 设计一个在链式存储结构上统计二叉树中结点个数的算法。 void countnode(bitree *bt,int &count) if(bt!=0) count+; countnode(bt-lchild,count); countnode(bt-rchild,
41、count); 2. 2. 设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。 typedef struct int vertexm; int edgemm;gadjmatrix; typedef struct node1int info;int adjvertex; struct node1 *nextarc;glinklistnode; typedef struct node2int vertexinfo;glinklistnode *firstarc;glinkheadnode; void adjmatrixtoadjlist(gadjmatrix g1 ,glinkheadnode
42、g2 ) int i,j; glinklistnode *p; for(i=0;i=n-1;i+) g2i.firstarc=0; for(i=0;i=n-1;i+) for(j=0;jadjvertex=j; p-nextarc=gi.firstarc; gi.firstarc=p; p=(glinklistnode *)malloc(sizeof(glinklistnode);p-adjvertex=i; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 23 页 -
43、 - - - - - - - - 第 15 页 共 23 页 p-nextarc=gj.firstarc; gj.firstarc=p; 2015 年考研计算机数据结构试题及答案（4）2015年考研计算机数据结构试题（4）一、选择题 (30 分) 1. 设某无向图有 n 个顶点，则该无向图的邻接表中有( ) 个表头结点。(A) 2n (B) n (C) n/2 (D) n(n-1) 2. 设无向图 G中有 n 个顶点，则该无向图的最小生成树上有( ) 条边。(A) n (B) n-1 (C) 2n (D) 2n-1 3. 设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第
44、一个关键字45 为基准而得到的一趟快速排序结果是( ) 。(A) 40 ，42，60，55，80，85 (B) 42 ，45，55，60，85，80 (C) 42 ，40，55，60，80，85 (D) 42 ，40，60，85，55，80 4.( )二叉排序树可以得到一个从小到大的有序序列。(A) 先序遍历 (B) 中序遍历 (C) 后序遍历 (D) 层次遍历5. 设按照从上到下、从左到右的顺序从1 开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为( ) 。(A) 2i+1 (B) 2i (C) i/2 (D) 2i-1 6. 程序段 s=i=0;do i=i+1; s=s+
45、i;while(inext=0 (C) head-next=head (D) head!=0 8. 设某棵二叉树的高度为10，则该二叉树上叶子结点最多有( ) 。(A) 20 (B) 256 (C) 512 (D) 1024 9. 设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90 需要比较的关键字个数为 ( ) 。(A) 1 (B) 2 (C) 3 (D) 4 10. 设指针变量 top 指向当前链式栈的栈顶，则删除栈顶元素的操作序列为( ) 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - -
46、 - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 23 页 - - - - - - - - - 第 16 页 共 23 页(A) top=top+1; (B) top=top-1; (C) top-next=top; (D) top=top-next; 二、判断题 (20 分) 1. 不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。( ) 2. 当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。( ) 3. 设某堆中有 n 个结点，则在该堆中插入一个新结点的时间复杂度为O(log2n) 。( ) 4. 完全二叉树中
47、的叶子结点只可能在最后两层中出现。( ) 5. 哈夫曼树中没有度数为1 的结点。 ( ) 6. 对连通图进行深度优先遍历可以访问到该图中的所有顶点。( ) 7. 先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。( ) 8. 由树转化成二叉树，该二叉树的右子树不一定为空。( ) 9. 线性表中的所有元素都有一个前驱元素和后继元素。( ) 10. 带权无向图的最小生成树是唯一的。( ) 三、填空题 (30 分) 1. 1. 设指针变量 p 指向双向链表中的结点A，指针变量 s 指向被插入的结点 X，则在结点 A的后面插入结点X的操作序列为 _=p;s-right=p-right;_=s;
48、p-right-left=s;(设结点中的两个指针域分别为left和 right)。2. 2. 设完全有向图中有n 个顶点，则该完全有向图中共有_条有向条 ; 设完全无向图中有 n 个顶点，则该完全无向图中共有_条无向边。3. 3. 设关键字序列为 (Kl ，K2，, ， Kn)，则用筛选法建初始堆必须从第_个元素开始进行筛选。4. 4. 解决散列表冲突的两种方法是_ 和_ 。5. 5. 设一棵三叉树中有50 个度数为 0 的结点， 21 个度数为 2 的结点，则该二叉树中度数为 3 的结点数有 _个。6. 6. 高度为 h 的完全二叉树中最少有 _个结点，最多有 _个结点。7. 7. 设有一
49、组初始关键字序列为(24，35，12，27，18，26)，则第 3 趟直接插入排序结束后的结果的是 _ 。8. 8. 设有一组初始关键字序列为(24，35，12，27，18，26)，则第 3 趟简单选择排序结束后的结果的是 _ 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 23 页 - - - - - - - - - 第 17 页 共 23 页9. 9. 设一棵二叉树的前序序列为ABC ，则有 _ 种不同的二叉树可以得到这种序列。10. 10. 下面程序段的功能是实
50、现一趟快速排序，请在下划线处填上正确的语句。struct record int key;datatype others; void quickpass(struct record r, int s, int t, int &i) int j=t; struct record x=rs; i=s; while(i while (ix.key) j=j-1; if (i= i=i+1; while (_) i=i+1; if (i _; 四、算法设计题 (20 分) 1. 1. 设计在链式结构上实现简单选择排序算法。2. 2. 设计在顺序存储结构上实现求子串算法。3. 3. 设计求结点在二叉排序树