湖北工业大学二八年招收硕士学位研究生试卷则从顶点 A 出发进行深度优先遍历可以得到的序列是 : A.ACEDBFG B.ACDGFBE C.AECDBGF D.ABDGFEC 9 在对 n 个元素的序列进行排序时, 堆排序所需要的附加存储空间是 ( ) A. O(log 2 n) B. O(1)

Size: px

Start display at page:

Download "湖北工业大学二八年招收硕士学位研究生试卷则从顶点 A 出发进行深度优先遍历可以得到的序列是 : A.ACEDBFG B.ACDGFBE C.AECDBGF D.ABDGFEC 9 在对 n 个元素的序列进行排序时, 堆排序所需要的附加存储空间是 ( ) A. O(log 2 n) B. O(1)"

彬亭包
6 years ago
Views:

1 二八年招收硕士学位研究生试卷试卷代号 917 试卷名称数据结构 1 试题内容不得超过画线范围, 试题必须打印, 图表清晰, 标注准确 2 考生请注意 : 答案一律做在答题纸上, 做在试卷上一律无效一单项选择题 ( 在每小题列出四个供选择的答案 A B C D 中, 选一个正确的答案, 将其代号填在答卷纸相应题号后的下横线上, 每小题 2 分, 共 20 分 ) 1 以下术语与数据的存储结构无关的是( ) A. 栈 B. 哈希表 C. 双向链表 D. 线索二叉树 2 在一个以 h 为头指针的双向循环链表中, 指针 p 所指的元素是尾元素的条件是 ( ) A. p==h B. h->rlink==p C. p->llink==h D. p->rlink==h 3 设栈 S 和队列 Q 的初始状态为空, 元素 a,b,c,d,e,f 依次通过栈 S, 一个元素出栈后即进队列 Q, 若 6 个元素出队的序列是 a,c,f,e,d,b, 则栈 S 的容量至少应该是 ( ) A. 6 B. 5 C. 4 D. 3 4 用循环链表表示队列, 设队列的长度为 n, 若只设尾指针, 则出队和入队的时间复杂度分别为 ( ) A.O(1),O(1) B. O(1),O(n) C. O(n),O(1) D. O(n),O(n) 5 设串 s1= ABCDEFG, s2= 12345, 则 strconcat (strsub (s1, 2, strlen(s2)), strsub (s1, strlen(s2), 7)) 的结果串是 ( ) A.BCDEF B.BCDEFG C.EFG D.BCDEEFG 6 某二叉树 T 有 n 个结点, 设按某种顺序对 T 中的每个结点进行编号, 编号为 1,2,, n, 且有如下性质 :T 中任一结点 V, 其编号等于 V 左子树上的最小编号减 1, 而 V 的右子树的结点中, 其最小编号等于 V 左子树上结点的最大编号加 1 这时是按( ) 编号的 A. 中序遍历序列 B. 前序遍历序列 C. 后序遍历序列 D. 层次遍历序列 7 分别以下列序列构造二叉排序树, 与用其它三个序列所构造的结果不同的是 ( ) A.(15,13,14,6,17,16,18) B.(15,17,16,18,13,6,14) C.(15,6,13,14,17,16,18) D. (15,13,6,14,17,18,16) 8 已知由 7 个顶点组成的无向图的邻接矩阵为 : A B C D E F G A B C D E F G 第 1 页共 4 页

2 湖北工业大学二八年招收硕士学位研究生试卷则从顶点 A 出发进行深度优先遍历可以得到的序列是 : A.ACEDBFG B.ACDGFBE C.AECDBGF D.ABDGFEC 9 在对 n 个元素的序列进行排序时, 堆排序所需要的附加存储空间是 ( ) A. O(log 2 n) B. O(1) C. O(n) D. O(nlog 2 n) 10 采用快速排序方法对一组数据 (43,3,43,33,38,78,73) 进行排序, 则以 43 为基准进行第一趟划分后数据的排序为 ( )( 按递增序 ) A.(33, 3, 38, 43, 43, 73, 78) B.(3, 33, 38, 43, 43, 78, 73) C.(3, 33,38, 43, 43, 73, 78) D.(38, 3, 43, 33, 43, 78, 73) 二填空题 ( 每小题 2 分, 本题共 20 分 ) 1 在下面的程序段中, 对 x 赋值的语句的频度为 for(i=1; i<=n; i++) for(j=1; j<=i; j++) for(k=1; k<=j; k++) x=x+1; 2 线性表 L=(a 1,a 2,,a n ) 用数组表示, 假如仅在 a i 与 a i+1 (1 i n-1) 之间插入元素, 且插入元素的概率相同, 则插入一个元素平均需要移动元素的个数为 3 用 PUSH 表示入栈操作,POP 表示出栈操作, 若元素入栈的顺序为 12345, 经过操作后, 出栈序列为 23, 栈内序列为 145, 相应的 PUSH 和 POP 的操作串为 4 用一个大小为 8 的数组来实现循环队列,front 为当前队列头元素的前一位置,rear 为队尾元素的位置, 当 rear 和 front 值分别为 2 7 时, 则当前队列中的元素的个数为 5 设定权集 w=1,2,4,6,8,9, 构造关于 w 的哈夫曼树, 则其带权路径长度 WPL= 6 若对满二叉树中的结点逐层编号 ( 层号由小到大, 同一层中从左到右 ), 根结点编号为 1, 其它依次为 2,3,, 则编号为 n 的结点的父结点编号为 7 对有 17 个元素的有序表 A[1..17] 作二分查找, 在查找其等于 A[7] 的元素时, 被比较的元素的下标依次是 8 设哈希表长为 17, 哈希函数为 H(K)=K mod 17 采用线性探测法处理冲突, 将关键字序列 26,25,72,38,8,18,59 依次存储到散列表中查找元素 59 需要搜索次数是 9 在执行冒泡排序前, 如果待排序文件中的 n 个记录顺序是逆序的, 则比较次数为 10 设有 n 个结点的完全二叉树按层次序顺序存放在数组 A[MAXSIZE] 中, 假设第一元素的下标为 0, 则其下标值最大的分支结点下标为三解答以下问题 ( 本题共 72 分 ) 1 设有一带头结点的非空单链表头指针为 head,p 结点 ( 指针为 P) 既不是首元结点, 也不是尾元结点 (1) 试写出删除 P 结点的直接后继结点的语句序列 ;(6 分 ) (2) 试写出删除 P 结点的直接前趋结点的语句序列 (10 分 ) 2 假设循环队列定义为 : #define maxqsize 101 /* 设置队列的最大长度为 100 */ typedef struct sqque 第 2 页共 4 页

3 湖北工业大学二八年招收硕士学位研究生试卷 elementype *base; /* 初始化的动态分配存储空间 */ int length; /* 队列长度 */ int rear ; /* 队尾指针 */ sqque; (1) 写出判断队列满和空的条件 ;(4 分 ) (2) 写出插入和删除一个元素的算法的关键语句 (12 分 ) 3 已知一棵树的先根序遍历序列为 ABEFJCDGHKLI, 后根序遍历序列为 EJFBCGKLHIDA (1) 画出该树的树形逻辑结构图 ;(5 分 ) (2) 求结点 D 的度和该树的度 ;(4 分 ) (3) 画出由该树变换而来的二叉树 (5 分 ) 4 设 AOE 网的事件集为 V=V1,V2,V3,V4,V5,V6,V7, 用 (Vi,Vj,w) 表示活动, 其中 Vi, Vj 分别表示第 i 和第 j 个事件,w 表示从 Vi 到 Vj 的持续时间, 活动集为 E=(V1,V2,10), (V1,V3,8),(V1,V4,20),(V2,V4,5),(V3,V4,7),(V3,V5,20),(V4,V6,6),(V5,V6,9),(V5,V7,2), (V6,V7,2) (1) 画出它的邻接表 ( 表结点按顶点编号递减序排列 );(12 分 ) (2) 写出每个活动的最早开始时间和最迟开始时间 ;(10 分 ) (3) 写出从 V1 到 V7 的所有关键路径 (4 分 ) 四算法填空题 ( 每空 2 分, 本题共 18 分 ) 1 设 h 是无头结点的单链表下列程序的功能是, 如果线性表 h 的长度不小于 2, 则将首元结点删除并插入到表尾请在空格处填上适当的语句, 使算法完整 typedef struct node elementype data; struct node *next; node, *linklist; void change(linklist &h) linklist p,q; if(h&&h->next) q=h; h= (1) p=h; while(p->next)(2); (3); (4); 2 假设图采用邻接表的存储定义下面是从图 G 的顶点 v 出发, 对从 v 可达的顶点进行广度优先遍历的算法, 请在空格处填上适当的语句, 使算法完整第 3 页共 4 页

4 湖北工业大学二八年招收硕士学位研究生试卷 void BFS(ALgraph G, int v) int queue[maxver],front,rear; listnode *p; front=rear=0; printf(g.vexs[v].data); visited[v]=1; (1) ; while( (2) ) v=queue[++front]; p= (3) ; while(p!=null) if(visited[p->adjvex]= =0) v= (4) ; printf(g.vexs[v].data); visited[v]=1; queue[++rear]=v; (5) ; 五算法设计 :( 要求用类 C 语言编写, 并对所用参数和变量在适当位置加注释 )( 本题 20 分 ) 试编写一个函数, 打印输出二叉排序树中关键字的值大于 x 且最靠近 x 的值要求使用非递归算法设二叉树的存储定义为 : typedef struct node int data; struct node *lchild,*rchild; BSTNode,*BSTree; 第 4 页共 4 页

5 二八年招收硕士学位研究生数据结构试题答案一单项选择题 ( 在每小题列出四个供选择的答案 A B C D 中, 选一个正确的答案, 将其代号填在答卷纸相应题号后的下横线上, 每小题 2 分, 共 20 分 ) 1 A. 2 D 3 C 4 A 5 D 6 B 7 C 8 C 9 B 10 D 二填空题 ( 每小题 2 分, 本题共 20 分 ) 1 n(n+1)(n+2)/6 O(n 3 ) 2 n/2 3 PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH n/2 7 A[9] A[4] A[6] A[7] n(n-1)/2 10 n/2-1 三解答以下问题 : 1 (1)q=p->next ; (2 分 ) p->next=q->next; (2 分 ) free(q); (2 分 ) (2)q=l; (2 分 ) while(q->next->next!=p)q=q->next; (2 分 ) p=q->next; (2 分 ) q->next=p->next; (2 分 ) free(p); (2 分 ) 2 (1) 队列为满为条件为 q.length==maxqsize (2 分 ) 队列为满为条件为 q.length==0 (2 分 ) (2) 插入元素的操作 : if(q.length==maxqsize)return error; (1.5 分 ) q.rear=(q.rear+1)%maxqsize; (1.5 分 ) q.base[q.rear]=x; (1.5 分 ) q.lenth++; (1.5 分 ) 删除元素的操作 : if(q.length==0)return error;(1.5 分 ) head=(q.rear-q.length+1)%maxqsize; (1.5 分 ) x=q.base[head]; (1.5 分 ) length--;(1.5 分 ) 3 (1) 画出该树的树形逻辑结构图 ;(5 分 ) (2) 树的度 :3(2 分 ) 结点 D 的度 :3(2 分 ) (3) 由该变换而来的二叉树 (5 分 ) B A C D E F G H J K L I E J B F A C G K D H L I

6 4 V V 2 20 V V 4 6 V5 9 2 V 6 2 V 7 (a) AOE 网 (1) (12 分 ) [1] 0 indegree first adjvex weight next ^ [2] 1 [3] 1 [4] 1 [5] 2 [6] 1 [7] 1^ 4 5 ^ 5 20 ^ 6 6 ^ ^ 4 7 ^ 6 9 ^ (2) (10 分 ) (b) 邻接表存储表示顶点 Ve Vl 活动 Ae Al V1 0 0 (V1,V2,10) 0 16 V (V1,V4,20) 0 11 V3 8 8 (V1,V3,8) 0 0 V (V2,V4,5) V (V3,V4,7) 8 24 V (V3,V5,20) 8 8 V (V4,V6,6) (V5,V6,9) (V5,V7,2) (V6,V7,2)) (3) (4 分 ) 关键路径为 :(V1,V3),(V3,V5),(V5,V6), (V6,V7) 五算法分析题 ( 每空 2 分, 共 18 分 ) 1 (1)h->next; (2)p=p->next (3)p->next=q; (4)q->next=NULL

7 2 (1) queue[++rear]=v (2)front!=rear (3)G.vexs[v].first; (4)p->adjvex (5)p=p->next 六 (20 分 ) #define INFINITY INT_MAX typedef struct node int data; struct node *lchild,*rchild; BSTNode,*BSTree; void printpost_x(bstree t, int x) BSTree stack[smaxsize],p=t; int top; int last=infinit; while(p!=null top>0) if(p!=null) stack[++top]=p; p=p->lchildt; else p=stack[top--]; if(last==x) printf(p->data); exit(); else last=p->data; p=p->rchild; printf( no node find );

四读算法 ( 每题 7 分, 共 14 分 ) 1. (1) 查询链表的尾结点 (2) 将第一个结点链接到链表的尾部, 作为新的尾结点 (3) 返回的线性表为 (a 2,a 3,,a n,a 1 ) 2. 递归地后序遍历链式存储的二叉树五法填空 ( 每空 2 分, 共 8 分 ) true B

四读算法 ( 每题 7 分, 共 14 分 ) 1. (1) 查询链表的尾结点 (2) 将第一个结点链接到链表的尾部, 作为新的尾结点 (3) 返回的线性表为 (a 2,a 3,,a n,a 1 ) 2. 递归地后序遍历链式存储的二叉树五法填空 ( 每空 2 分, 共 8 分 ) true B 数据结构试卷 ( 一 ) 参考答案一选择题 ( 每题 2 分, 共 20 分 ) 1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A 二填空题 ( 每空 1 分, 共 26 分 ) 1. 正确性易读性强壮性高效率 2. O(n) 3. 9 3 3 4. -1 3 4 X * + 2 Y * 3 / - 5. 2n n-1 n+1 6. e 2e 7. 有向无回路

湖北工业大学二 八年招收硕士学位研究生试卷 则从顶点 A 出发进行深度优先遍历可以得到的序列是 : A.ACEDBFG B.ACDGFBE C.AECDBGF D.ABDGFEC 9 在对 n 个元素的序列进行排序时, 堆排序所需要的附加存储空间是 ( ) A. O(log 2 n) B. O(1)

湖北工业大学二八年招收硕士学位研究生试卷则从顶点 A 出发进行深度优先遍历可以得到的序列是 : A.ACEDBFG B.ACDGFBE C.AECDBGF D.ABDGFEC 9 在对 n 个元素的序列进行排序时, 堆排序所需要的附加存储空间是 ( ) A. O(log 2 n) B. O(1)