当前位置: 首页 > >

华侨大学2013年《850数据结构与C++》考研专业课真题试卷

发布时间:

华侨大学 2013 年硕士研究生入学考试专业课试卷 (答案必须写在答题纸上) 招生专业 科目名称 计算机技术 数据结构与 C++ 科目代码 850 第一部分 数据结构(共 75 分) 一、单项选择题(每小题 2 分,共 24 分) 1.执行下面程序段时,则 S 语句的语句频度是() 。 for(int i =1;i<=n;i++) for (int j =1; j <=i ; j++) S; 2 A) n B) n2/2 C) n(n+1) D) n(n+1)/2 2. 在一个不带头结点的单链表 HL 中, 若要向表头插入一个由指针 p 指向的结点, 则执行( )。 A)HL=p;p->next=HL; B)p->next=HL;HL=p; C)p->next=HL;p=HL; D)p->next=HL->next;HL->next=p; 3.设栈 S 和队列 Q 的初始状态皆为空,元素 a1,a2,a3,a4,a5 和 a6 依次通过一个栈, 一个元素出栈后即进入队列 Q,若 6 个元素出队列的顺序是 a3,a5,a4,a6,a2,a1 则栈 S 至少应该容纳()个元素。 A)3 B)4 C)5 D)6 4. 一棵树高为 K(K≥1)的完全二叉树至少有()个结点。 A)2k-1 B)2k C)2k+1 D)log2k 5.由权值分别为 3,8,6,2,5 的叶子结点生成一棵赫夫曼树,它的带权路径长度为() 。 A) 24 B)48 C)72 D)53 6. 假设一个有 n 个顶点和 e 条弧的有向图用邻接表表示,则删除与某个顶点 vi 相关的边 的时间复杂度是() 。 A)O(n) B)O(e) C)O(n+e) D)O(n*e) 7. 图的深度优先遍历类似于树的() 。 A)先序遍历 B)中序遍历 C)后序遍历 D)层次遍历 8. 对一棵二叉排序树进行()遍历,可以得到该二叉树的所有结点按值从小到大排列的序 列。 A)前序 B)后序 C)中序 D)按层次 9.设散列表长 m=14,散列函数 H(K)=K%11,已知表中已有 4 个结点:r(15)=4; r(38)=5; r(61)=6;r(84)=7,其他地址为空,如用二次探测再散列处理冲突,关键字为 49 的结点地 址是() 。 A)8 B)3 C)5 D)9 10. 用某种排序方法对关键字序列(23,72,21,47,15,27,59,35,20)进行排序时, 共 10 页 第 1 页 1 前两趟的结果情况如下: 15,72,21,47,23,27,59,35,20 15,20,21,47,23,27,59,35,72 则所采用的排序方法是() 。 A)选择排序 B)起泡排序 C)归并排序 D)快速排序 11.n 个顶点的无向图中含有边的数目最多为() 。 A)n-1 B)n C)n(n-1)/2 D) n(n-1) 12.由权值分别为 11,8,6,2,5 的叶子结点生成一棵赫夫曼树,它的带权路径长度 WPL 为() 。 A)24 B)71 C)48 D)53 二、简答与应用题(30 分) 1. (8 分)假设链队列带头结点,其出队操作如下: Status DnQueue_L(LinkQueue &Q ,ElemType &e){ //链队列 Q 出队,出队元素赋值给 e 中 if(Q.front = = Q.rear) return ERROR; p = Q.front->next; e = p->data; Q.front ->next = p->next; if(Q.rear = = p) Q.rear = Q.front; //问题(1) free(p); return OK; }// DeQueue_L (1) (4 分)此处的 if 语句起什么作用(含义)? 对出队前若队列里只有一个结点的情况处理,此时需要修改 Q.rear 值。 (2) (4 分) 假设链队列不带头结点, 请补充下面的代码, 以实现类似的链队列出队操作。 Status DnQueue_L(LinkQueue &Q ,ElemType &e){ //不带头结点的链队列 Q 出队,出队元素赋值给 e 中 if(Q.front==NULL) return ERROR; //空队列 if(Q.front==Q.rear){ //只有一个结点的处理 e=Q.front.data; p=Q.front; ______ (1) _____; free(p); return OK; } p = Q.front; e = p->data; ______(2) ; ; free(p); return OK; 共 10 页 第 2 页 2 }// DeQueue_L 2. (8 分)请对下图所示的二叉树进行中序线索化,为每个空指针建立相应的前驱和后继, 请用虚线箭头在图中画出结果。 3. (8分)考虑无向网G: (1) (2分) 给出邻接表存储结构 (要求邻接表的每个顶点的邻接链表按结点域升序排列, 每一表结点包含所表示的边的权值) 。 (2) (2分)请给出从顶点A开始的深度优先顶点访问序列(要求根据邻接表进行遍历) 。 (3) (4分)根据克鲁斯卡尔(Kruscal)算法,画出无向图G的最小生成树。 C 4 A 2 3 E D B 2 6 F 1 5 G 无向网 G 4 4. (6 分)有一组关键字序列{26,38,73,21,54,35,167,32,7,223,52},试用哈希函数 H(key)=key mod 13 和链地址(拉链)法解决冲突方法构造这组关键字的哈希表(设哈希表 的长度为 15) 。 三、算法设计题(21 分) 1. (10 分)设单向链表的类型定义如下: typedef int ElemType; //设表中元素类型为 int typedef struct LNode{ ElemType data; Node* next; }*



友情链接: year2525网 工作范文网 QS-ISP 138资料网 528200 工作范文网 baothai 表格模版