2019年全国硕士研究生统一入学考试自命题试题(A卷)
********************************************************************************************
招生专业与代码:计算机科学与技术、软件工程、网络空间安全、工程硕士
研究方向:计算机系统结构081201,计算机软件与理论081202,计算机应用技术081203,软件工程083500,计算机技术(专业学位) 085211,网络空间安全083900
考试科目名称及代码:数据结构830
考生注意:所有答案必须写在答题纸(卷)上,写在本试题上一律不给分。 |
一、 单项选择题(每题2分,共30分) A.不一定相同 B.互为逆序 C.都不相同 D.都相同 A. 18 B. 14 C. 15 D.16 3. 在一个具有n个顶点的有向图中,若所有顶点的入度数之和为m,则所有顶点的度数之和为( )。 A.m B.m-1 C.m+1 D.2m A. 被排序的数据量太大. B. 被排序数据中含有多个相同的关键字 C. 被排序的数据完全无序 D. 被排序的数据已基本有序 5. 一组记录的关键字为(45,80,55,40,42,85), 则利用堆排序的方法建立的初始堆为( )。 A. (80,45,55,40,42,85) B. (85,80,55,40,42,45) C. (85,80,55,45,42,40) D. (85,55,80,42,45,40) 6. 对有18个元素的有序表(下标为1~18)作折半查,则查A[3]的比较序列的下标为 ( )。 A. 1,2,3 B. 9,5,2,3 C. 9,5,3 D. 9,4,2,3 7. 具有n个顶点的完全有向图的边数为( )。 A. n(n-1)/2 B. n(n-1) C. n2 D. n2-1 8. 利用逐点插入法建立序列(50,72,43,85,75,20,35,45,65,30)对应的二叉排序树以后,查元素35要进行( )。 A. 4次 B. 5次 C. 3次 D. 2次 9. 判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以用( )。 A.求最短路径的Floyd方法 B.求最短路径的Dijkstra方法 C.广度优先遍历算法 D.深度优先遍历算法 10. 对于一个具有n个顶点的无向连通图,它包含的连通分量的个数为( )。 A.0 B.1 C.n D.n+1 11. 在一个单链表中,若p所指的结点不是最后一个结点,在p之后插入s所指的结点, 则执行( )。 A. s->next=p; p->next=s B. p->next=s; s->next=p C. p=s; s->next=p->next D. s->next=p->next; p->next=s |
考试科目: 数据结构 共5 页,第 1 页
12. 设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 13. 设输入元素1,2,3,P,A,输入次序为:123PA,元素经过栈后到达输出序列。当所有元素均达到输出序列,下面( )序列可以作为高级语言的变量名。 A. 123PA B. PA321 C. 12AP3 D. PA123 14. 在一个链队列Q中,删除一个结点需要执行的指令是( )。 A. Q.rear=Q.front->next; B. Q.rear->ar->next->next; C. Q.front->next=Q.front->next->next; D. Q.ar->next; 15. 如果T2是由树T转换而来的二叉树,那T中结点的后序就是T2中结点的 ( )。 A. 先序 B. 中序 C. 后序 D. 层次序 二.填空题(每空2分,共20分) 1. 设根结点在第一层,那么具有n个结点的完全二叉树,其高度为 。 2. 对于一个循环队列Q[0..m-1],队头、队尾指针分别为f、r,其判空的条件是 ,判满的条件是 。 3. 在堆排序,希尔排序,快速排序,归并排序算法中,占用辅助空间最多的是 。 4. 已知二维数组A[m][n]采用行序为主序存储,每个元素占k个存储单元,并且第一个元素的存储地址是Loc(A[0][0]), 则A[i][j]的地址是 。 5. 若某记录序列的关键字序列是(235,346,021,558,256),用链式基数排序方法排序,第一次收集的结果是 。 6.设Hash表为m=11,散列函数H(k)=k%11,表中已有4个结点,地址分别为:addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7,其余地址为空。如果用二次探测再散列处理冲突,关键字为49的结点的地址是 。 7.在一个3阶的B-树上,每个结点包含的子树相同,最多为 个结点,最少为 个结点。 8.一个连通图的 是一个极小连通子图。 三.判断题(每题1分,共102019年考研数学三答案分,正确的选t,错误的选f) 1.对于n个记录的集合进行冒泡排序,在最坏情况下的时间复杂度是O(n2)。 ( ) 2.包含两个结点的所有二叉树都是相同的。( ) 3.一个图按广度优先遍历的结果是唯一的。( ) 4.用Prime算法和Kruskal 算法求得的图的最小生成树一定相同。( ) 5.线性表中的每一个元素都有一个前驱和后继元素。( ) 6.在n个顶点的无向图中,若边数>n-1,则该图必是连通图。( ) 7.完全二叉树的某结点若无左孩子,则必是叶子结点。 ( ) 8.在B-树,有n棵子树的结点中有n个关键字。 ( ) 9.在一个有向图的邻接表或逆邻接表中,如果某个顶点的链表为空,则该顶点的度一定为零。( ) 10.用邻接矩阵法存储一个图时,在不考虑压缩存储的情况下,所占用的存储空间大小与图中结点的个数有关,而与图的边数无关。( ) |
考试科目: 数据结构 共5 页,第 2 页
四. 简答题(40分) 1. 设G为有n个顶点的无向连通图,证明G至少有n-1 条边。 (7分) 2. 什么是线索二叉树?一棵二叉树的中序遍历序列为djbaechif,前序遍历序列为abdjcefhi,请画出该二叉树的后序线索二叉树。(7分) 3. 已知某通讯电文仅有A、B、C、D、E、F六个字符构成,其出现频率分别为23,5,14,8,25,7,请给出他们的Huffman编码以及求解过程。(7分) 4、给定一棵二叉链表存储的二叉树,试用文字描述判定一棵二叉树是否是完全二叉树的算法基本思想。(7分) 5. 已知一棵完全二叉树共有67 个结点,试求: (7分) (1) 树的深度; (2) 度为1的结点数; (3) 叶子结点数; 6. 对给定的一组关键字序列(29,18,25,47,58,12,51,10), 写出用归并排序方法进行排序的变化过程。(5分) 五.算法填空(共2小题,每空2分,共20分) 1. 若二叉排序树T中存在其关键字等于 key 的数据元素时,则下面算法删除该数据元素结点,并返回TRUE;否则返回FALSE。请在________处填上适当内容,使其成为一个完整算法。 typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; Status DeleteBST(BiTree &T, KeyType key) { if (!T) return FALSE; else { if (EQ(key, T->data.key)) return Delete(T); else if (LT(key, T->data.key)) return DeleteBST(T->lchild, key); else return DeleteBST(T->rchild, key); } } |
考试科目: 数据结构 共5页,第 3 页
Status Delete(BiTree &p) { BiTree q, s; if (!p->rchild) { q = p; (1) free(q); } else if (!p->lchild) { q = p; (2) free(q); } else { q = p; (3) ; while ( (4) ) { q = s; s = s->rchild; } p->data = s->data; if ( q != p) q->rchild = s->lchild; else (5) free(s); } return TRUE; } 2. 下面是快速排序算法。请在__________处填上适当内容,使其成为一个完整算法。 #define Maxsize 100 typedef int keytype; typedef struct { keytype key; Infotype otherinfo; }RedType; typedef struct { RedType r[Maxsize+1]; int length; }SqList; void Qsort(SqList &L, int low, int high) { if (low<high) { pivotloc=Partition(L, low, high); (6) ; Qsort(L, pivotloc+1, high); } } |
考试科目: 数据结构 共5 页,第 4 页
int Partition(SqList &L,int low,int high) { L.r[0]=L.r[low]; pivotkey=L.r[low].key; while ( low<high ) { while (low<high&&L.r[high].key>=pivotkey) (7) ; L.r[low]=L.r[high]; while (low<high&&L.r[low].key<=pivotkey) (8) ; L.r[high]=L.r[low]; } L.r[low]= (9) ; return (10) ; } 六.编写算法(30分) 1. 试编写算法,从大到小输出二叉排序树中所有的值不小于x的关键字。(10分) 2. 设有一个由正整数组成的无序单链表,试编写算法实现下列功能:(10分) (1)出最小值结点,并输出该数值; (2)若该最小值是奇数,则将其与直接后继结点的数值交换;如该最小值是偶数,则将其直接后继结点删除。 3. 编写一个算法根据用户输入的偶对(以输入0表示结束)建立其有向图的邻接表(设有n个顶点)。(10分) |
考试科目: 数据结构 共5 页,第 5 页
发布评论