2019年重庆邮电大学数据结构考研真题A卷.doc-资料库

第1页 / 共7页

第2页 / 共7页

第3页 / 共7页

第4页 / 共7页

第5页 / 共7页

第6页 / 共7页

第7页 / 共7页

2019年重庆邮电大学数据结构考研真题A卷一、选择题（本大题共 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 C. 3 1 2 B. 3 2 1 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[l..n]中时，数组中第 i 个结点的左孩子为（）。 A. A[2i](2i=

8. 串的长度是指（）。 A.串中所含不同字母的个数 B．串中所含字符的个数 C.串中所含不同字符的个数 D．串中所含非空格字符的个数 9．循环队列存储在数组 A[0..m]中，则入队时的操作为（）。 A. rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1) 10．关键路径是事件结点网络中（）。 A. 从源点到汇点的最长路径 C. 最长回路 B. 从源点到汇点的最短路径 D. 最短回路二、填空题（本大题共 15 小题，每空 2 分，共 40 分） 1. 中缀算式（3+4X）-2Y/3 对应的后缀算式为 2. 在完全二叉树中，编号为 i 和 j 的两个结点处于同一层的条件是 3. 构造 n 个结点的强连通图，至少有 4. 设有一个空栈，栈顶指针为 1000H(十六进制)，现有输入序列为 a，b，c，d， e．经过条弧。。。 PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH 之后，输出序列是，而栈顶指针值是 H。设栈为顺序栈，每个元素占 4 个字节。 5．若串 S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘012345’,执行 concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8 ’),lengt h(S2)))，其结果为。 6．若一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为。 7．在有序表（12，24，36，48，60，72，84）中二分查找关键字 72 时所需进行的关键字比较次数为。 8．有向图的边集为{,, , , , }，该图的一

个拓扑排序为：。 9．当输入序列局部有序或元素个数较小时，在快速排序、选择排序、插入排序、归并排序、堆排序中，最佳的排序方法是。10．假设两个队列共享一个循环向量空间（参见右图），其类型 Queue2 定义如下： typedef struct{ DateType data[MaxSize]； int front[2],rear[2]； }Queue2；对于 i=0 或 1，front[i]和 rear[i]分别为第 i 个队列的头指针和尾指针。请对以下算法填空，实现第 i 个队列的入队操作。 int EnQueue (Queue2 *Q, int i, DateType x) {//若第 i 个队列不满，则元素 x 入队列，并返回 1；否则返回 0 if( i<0||i>1 ) return 0； if( Q－>rear[i] == Q－>front[ ] ) return 0； Q－>data[ ] = x； Q－>rear[i] = [ ] ; return1； } 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); } } 对于如下所示的二叉树 E. 画出执行上述算法后所建立的结构

F. 说明该算法的功能 9. 假设以 I 和 O 分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由 I 和 O 组成的序列，称可以操作的序列为合法序列，否则称为非法序列。 • • 下面所示的序列中哪些是合法的？ A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO 通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。（假定被判定的操作序列已存入一维数组 char A[ ]中, 若操作序列合法，返回true，否则返回 false）。 10. 已知一个连通图如下图所示，试给出图的邻接矩阵和邻接表存储示意图，若从顶点 v1 出发对该图进行遍历，分别给出一个按深度优先遍历和广度优先遍历的顶点序列. D. 图的邻接矩阵 E. 邻接表存储示意图 F. 从 v1 开始的深度优先遍历的顶点序列 G. 分析在深度遍历过程中，分别使用邻接矩阵和邻接表存储的算法复杂度 H. 讨论在图遍历问题中，这两种存储方式的优劣 11. 一棵二叉树的先序序列为 ABCDGEF，中序序列为 CBDGAFE。(1)请画出该二叉树 (2)将二叉树转换为相应的森林 12. 请阅读下列算法，回答问题 sort（r, n） { for (i=2; i<=n; i++) { x=r(i); r(0)=x; j=i- 1; while( x

r(j+1)=r (j); j=j-1; } r(j+1)=x; } } 16. 17. 18. 19. 这是什么类型的排序算法，该排序算法稳定吗？设置 r(0)的作用是什么？若将 while 语句中判断条件改为 x<=r(j), 该算法将会有什么变化？若将 while 语句中判断条件改为 x<=r(j), 该算法是否还能正确工作？四、程序设计题（本大题共 2 小题，每小题 15 分，共 30 分） 1. 设有大小不等的 n 个数据组, 其数据总量为 m，顺序存放在空间区 D 内,每个数据占一个存储单元，数据组的首地址由数组 S 给出，（如下图所示），试编写将新数据 x 插入到第 i 个数据组的末尾且属于第 i 个数据组的算法，插入后，空间区 D 和数组 S 的相互关系仍保持正确。

2. 快速排序算法中，如何选取一个界值（又称为轴元素），影响着快速排序的效率，而且界值也并不一定是被排序序列中的一个元素。例如，我们可以用被排序序列中所有元素的平均值作为界值。用 C 语言编写算法实现以平均值为界值的快速排序方法（注：待排序数据存储在数组 R[ ]中, 数组最小下标为 S，数组最大下标为 T）。

资料库

2019年重庆邮电大学数据结构考研真题A卷.doc

相关推荐

考研

热门标签

最新资料