注:本套试卷由强连通计算机考研完成解析,但难免有疏漏,如果发现错误请及时与我们反馈。 勘误:对微信公众号“强连通计算机考研”回复“重邮802勘误”。
2019年答案 一、选择题(本大题共 10 小题,每小题 2 分,共 20 分) 二、填空题(本大题共 15 小题,每空 2 分,共 40 分) 三、问答题(本大题共 6 小题,每小题 10 分,共 60 分)四、程序设计题(本大题共 2 小题,每小题 15 分,共 30 分) 2019年试题 一、选择题(本大题共 10 小题,每小题 2 分,共 20 分)1、对于双向循环链表,每个结点有两个指针域 next 和 prior,分别指向前驱和后继。在 p 指针所指向的结点之后插入 s 指针所指结点的操作应为( )。 A. p->next = s; s->prior = p; p->next->prior = s; s->next = p->next; B. p->next = s; p->next->prior = s; s->prior = p; s->next = p->next; C. s->prior = p; s->next = p->next; p->next = s; p->next->prior = s; D. s->prior = p; s->next = p->next; p->next->prior = s; p->next = s;
2、由 abc,3 个结点可以构造出多少种不同的二叉树?( ) A. 2 B. 3 C. 4 D. 5
3、设有数组 A[i,j],数组的每个元素长度为 3 字节,i 的值为 1 到 8 ,j 的值为 1 到10,数组从内存首地址BA开始顺序存放,当用以列为主存放时,元素A[5, 8]的存储首地址为( )。 A. BA+141 B. BA+180 C. BA+222 D. BA+225
4、一个栈的输入序列为 1 2 3,则下列序列中不可能是栈的输出序列的是( )。 A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3
5、下述编码中哪一个不是前缀码( )。 A.(00,01,10,11) B.(0,1,00,11) C.(0,10,110,111) D.(1,01,000,001)
6、当一棵有 n 个结点的二叉树按层次从上到下,同层次从左到右将数据存放在 一维数组 A[1…n]中时,数组中第 i 个结点的左孩子为( )。 A. A[2i](2i=rear[i] == Q->front__________ ) return 0; Q->data __________ = x;Q->rear[i] = __________;return 1;}
11、高度为 8 的平衡二叉树的结点数至少有________个。 12、文件由_____组成;记录由_____组成。 13、对于一个具有 n 个结点的单链表,在已知的结点*p 后插入一个新结点的时间复杂度为_____,在给定值为 x 的结点后插入一个新结点的时间复杂度为______。 14、在 n 个记录的有序顺序表中进行折半查找,最大比较次数是______。 15、求从某源点到其余各顶点的 Dijkstra 算法在图的顶点数为 10,用邻接矩阵表示图时计算时间约为 10ms,则在图的顶点数为 40,计算时间约为______ms。
三、问答题(本大题共 6 小题,每小题 10 分,共 60 分)1、一个线性表为 B=(12,23,45,57,20,03,78,31,15,36),设散列表 为 HT[0…12],散列函数为 H(key)= key % 13 并用线性探查法解决冲突,请画出散列表,并计算等概率情况下查找成功的平均查找长度。
2、已知二叉树的存储结构为二叉链表,阅读下面算法。
typedef struct node { DateType data;Struct node * next; } ListNode;typedef ListNode *LinkList; LinkList Leafhead = NULL;void Inorder (BinTree T) {LinkList s; if(T){Inorder(T->lchild);if ((!T->lchild)&&(!T->rchild)) {s = (ListNode*)malloc(sizeof(ListNode)); s->data=T->data; s->next=Leafhead;Leafhead=s;}Inorder(T->rchild); }}对于如下所示的二叉树 (1)画出执行上述算法后所建立的结构 (2)说明该算法的功能
3、假设以 I 和 O 分别表示入栈和出栈操作。栈的初态和终态均为空,入栈和出栈的操作序列可表示为仅由 I 和 O 组成的序列,称可以操作的序列为合法序列,否则称为非法序列。 (1)下面所示的序列中哪些是合法的? A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO (2)通过对(1)的分析,写出一个算法,判定所给的操作序列是否合法。(假 定被判定的操作序列已存入一维数组 char A[ ]中, 若操作序列合法,返回 true, 否则返回 false)。
4、已知一个连通图如下图所示,试给出图的邻接矩阵和邻接表存储示意图,若从顶点 v1 出发对该图进行遍历,分别给出一个按深度优先遍历和广度优先遍历的顶点序列:(1) 图的邻接矩阵 (2) 邻接表存储示意图 (3) 从 v1 开始的深度优先遍历的顶点序列、广度优先遍历的顶点序列 (4) 分析在深度遍历过程中,分别使用邻接矩阵和邻接表存储的算法复杂度 (5) 讨论在图遍历问题中,这两种存储方式的优劣
5、一棵二叉树的先序序列为 ABCDGEF,中序序列为 CBDGAFE。 (1)请画出该二叉树。 (2)将二叉树转换为相应的森林。
6、请阅读下列算法,回答问题
sort(r, n) {for (i=2; i