2001数据结构.pdf

一、选择题 （30分） 1. 在数据结构中，从逻辑上可以把数据结构分成（ ） （A）动态结构和静态结构 （B）紧凑结构和非紧凑结构（C）内部结构和外部结构 （D）线性结构和 非线性结构 2. 算法分析的两个主要方面是（ ） （A）数据复杂性和程序复杂性 （B）可读性和文档性 （C）时间复杂度和空间复杂度 （D）正确性和简单性 3. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ ）个元素。 （A） 8 （B）63.5 （C）63 （D）7 4.在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（ ） （A）s-next=p;p-next=s; （B） s-next=p-next;p-next=s; （C）s-next=p-next;p=s; （D）p-next=s;s-next=p; 5. 栈结构通常采用的两种存储结构是（ ） （A） 线性存储结构和链表存储结构（B） 散列方式和索引方式 （C） 链表存储结构和数组 （D）线性存储结构和非线性存储结构 6. 设一数列a，b，c，d，e，f，通过栈结构不可能排成的顺序数列为（ ）。 （A）c，b，e，f，d，a （B）a，e，d，f，b，c （C）b，d，c，e，a，f （D）d，e，c，f，b，a 7. 设循环队列 Q[N]的头尾指针为 F、R，头指针 F 总是指在队列中的第一个元素的前一位置，则队列中元 素计数为（ ）。 （A）R-F（B）N-(R-F)（C）(R-F+N)%N（D）(F-R+N)%N 8. 设 字 符 串 s1=’ABCDEFG’,s2=’PQRST’, 则 运 算 s=strcat(strsub(s1,2,strlen(s2)),strsub (s1,strlen(s2),2))后结果为（ ）。 （A）‘BCQR’（B）’BCDEF’（C）’BCDEFG’（D）’BCDEFEF’ 9.设有一个二维数组A[10][15],数组按行存放，假设A[0][0]存放位置在644,每个元素占一个空间，则A[4][5] 在（ ）位置. (A) 672 （B）626 （C）709 （D）724 10.设二叉树根结点的层次为1，所有含有63个结点的二叉树中，最小高度是（ ） (A) 6 (B) 5 (C) 4 (D) 7 11.设结点 x 和结点 y 是二叉树 T 中的任意两个结点，若在前序序列中 x 在 y 之前，而在后序序列中 x 在 y 之后，则x和y 的关系是（ ） （A）x是y的左兄弟 （B）x是y的右兄弟 （C）y是x的祖先 （D）y是x的孩子 12.具有n个顶点的无向完全图的边数为（ ）。 2 2 （A） n(n-1)/2 （B）n(n-1) （C）n （D）n-1 13.请指出在顺序表(2,5,7,10,14,15,18,23,35,41,52)中，用二分法查找关键码12需做（）次关键码比较。 （A）5 （B）4 （C）3 （D）2 14.如果只想得到10240个元素序列中第5个最大元素之前的部分排序的序列，用（ ）方法最快。 (A)起泡排序 （B）快速排序 （C）简单选择排序 （D）堆排序 15.设有字符序列{Q、H、C、Y、P、A、M、S、R、D、F、X}，问新序列{F、H、C、D、P、A、M、Q、R、S、Y、 X}是下列哪个排序算法一趟扫描的结果。（ ） （A）起泡排序 （B） 初始步长为4的shell的排序 （C）以第一个元素为分界元素的快速排序（D）二路归并排序 二、填空题 （17分） 1．设有一对称矩阵 A[n][n]，按行优先次序存放在一维数组 S[m]中，在 S 中只存放 A 的下三角元素。请写