近两年的考研真题对大家具有重要价值!考研真题除了起到测验的作用外,也是风格的直接展现。文都考研小编为大家带来了2019年暨南大学830数据结构考研真题,一起看看吧。
考生注意:所有答案必须写在答题纸(卷)上,写在本试题上一律不给分。
一、 单项选择题(每题2分,共30分)
1. 在任意一棵二叉树的先序序列和后序序列中,各叶子之间的相对次序关系 ( )。
A.不一定相同 B.互为逆序 C.都不相同 D.都相同
2. 深度为4的二叉树至多有结点数为( )。
A. 18 B. 14 C. 15 D.16
3. 在一个具有n个顶点的有向图中,若所有顶点的入度数之和为m,则所有顶点的度数之和为( )。
A.m B.m-1 C.m+1 D.2m
4. 快速排序在( )情况下最不利于发挥其长处。
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->next=Q.rear->next->next;
C. Q.front->next=Q.front->next->next; D. Q.front=Q.rear->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分,共10分,正确的选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
{ 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
while (low
L.r[low]=L.r[high];
while (low
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 页
以上就是2019年暨南大学830数据结构考研真题考研真题,藉此我们可以看出暨南大学830数据结构考研真题真题趋势。更多院校830数据结构考研真题考研真题,持续更新中。