1、 数据结构 试 卷及答案 1算法分析的目的是 ( )。 A.找出数据结构的合理性 B.研究算法中输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2（ ）是具有相同特性数据元素的集合，是数据的子集。 A.数据符号 B.数据对象 C.数据 D.数据结构 3用链表表示线性表的优点是 ( )。 A.便于随机存取 B.花费的存储空 间比顺序表少 C.便于插入与删除 D.数据元素的物理顺序与逻辑顺序相同 4输入序列为（ A,B,C,D）不可能的输出有（ ）。 A.(A,B,C,D) B. (D,C,B,A) C. (A,C,D,B) D . (C,A,B,D) 5在数组表示的循
2、环队列中， front、 rear 分别为队列的头、尾指针， maxSize 为数组的最大长度，队满的条件是 ( )。 A. front=maxSize B. (rear+1)%maxSize=front C. rear=maxSize D. rear=front 6设有串 t=I am a good student ，那么 Substr(t,6,6)=（ ）。 A. student B. a good s C. good D. a good 7设有一个对称矩阵 A，采用压缩存储方式，以行序为主序存储 a11 为第一个元素，其存储地址为 1，每个元素占一个地址空 间，则 a85 地址为（ ）。
3、 A.23 B.33 C.18 D. 40 8已知广义表 LS=(A,(B,C,D),E)运用 head 和 tail 函数，取出 LS 中原子 b 的运算（ ）。 A. Gethead(Gethead(LS) B. Gettail(Gethead(LS) C. Gethead(Gethead(Gettail(LS) D. Gethead(Gettail(LS) 9若 已知一棵二叉树先序序列为 ABCDEFG，中序序列为 CBDAEGF，则其后序序列为( ) 。 A. CDBGFEA B. CDBFGEA C. CDBAGFE D. BCDAGFE 10下列存储形式中， ( ) 不是树的存储形
4、式。 A.双亲表示法 B.左子女右兄弟表示法 C.广义表表示法 D.顺序表示法 11对待排序的元素序列进行划 分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是 ( )。 A.直接选择排序 B.直接插入排序 C.快速排序 D.起泡排序 12采用折半查找方法进行查找，数据文件应为（ ），且限于（ ）。 A.有序表 顺序存储结构 B.有序表 链式存储结构 C.随机表 顺序存储结构 D.随机表 链式存储结构 13就平均查找速度而言，下列几种查找速度从慢至快的关系是（ ） A.顺序 折半 哈希 分块 B.顺序 分块 折半哈希 C.分块 折
5、半 哈希 顺序 D.顺序 哈希 分块 折半 14执行下面程序段时，执行 S 语句的次数为（ ） for(int I=1;Idata); if(p-rchild!=NULL) (3) ; stacktop=p-rchild; if( (4) ) top+; (5) ; 3.请在标号处填写合适的语句。完成下列程序。 (每空 1 分，共 5 分 ) int Binary_Search(S_TBL tbl， KEY kx) /* 在表 tbl中查找关键码为 kx 的数据元素，若找到返回该元素在表中的位置，否则，返回 0 */ int mid， flag=0； low=1； high=length； w
6、hile( 4.下面是一个采用直接选择排 序方法进行升序排序的函数，请在标号处填写合适的语句。 (每空 1 分，共 5 分 ) 程序： Void seletesort(int An,int n) int i,j,t,minval,minidx; for(i=1;i next; p- next=p- next- next; B、 p- next=p- next- next; C、 p=p- next; D、 p=p- next-next; 5.在一个链队列中 ,假定 front 和 rear 分别为队首和队后指针 ,则进行插入 S 结点的操作时应执行 _。 A、 front- next=s； f
7、ront=s； B、 s- next=rear; rear=s； C、 rear- next=s; rear=s； D、 s- next=front; front=s； 6.在一棵度为 3的树中度为 3的结点数为 3个 ,度为 2的结点数为 1个 ,度为 1的结点数为 1个 ,那么度为 0 的结点数为 _个 A、 6 B、 7 C、 8 D、 9 7.假定一棵二叉树的结点数为 33 个 ,则它的最小高度为 _,最大高度为 _ A、 4,33 B、 5,33 C、 6,33 D、 6,32 8. 在一棵完全二叉树中 ,若编号为 i 的结点有右孩子 ,则 该结点的右孩子编号为 _。 A、 2i B
8、、 2i+1 C、 2i-1 D、 i/2 9.在一个有向图中 ,所有顶点的入度之和等于所有弧数和 _倍。 A、 1 B、 2 C、 3 D、 4 10.对于一个具有 N 个顶点的图 ,若用邻接矩阵表示 ,则该矩阵的大小为 _。 A、 N B、 (N-1)2 C、 (N+1)2 D、 N2 11.已知一个图如图所示，在该图的最小生成树中各边上数值之和为 _。 A、 21 B、 26 C、 28 D、 33 12.已知一个图如图所示，由该图行到的一种拓朴序列为 A、 v1 v4 v6 v2 v5 v3 B、 v1 v2 v3 v4 v5 v6 C、 v1 v4 v2 v3 v6 v5 D、 v1
9、 v2 v4 v6 v3 v5 13.二维数组 M 的元素是 4 个字符（每个字符占一个存储单元）组成的串，行下标 i 的范围从 0 到 4，列下标 j 的范围从 0 到 5， M 按行存储时元素 M24的起始地址与 M 按列存储时元素 的起始地址相同。 A、 m24 B、 M42 C、 M31 D、 M31 14.具有 6 个结点的无向图至少应有 条边才能保证是连通图。 A、 5 B、 6 C、 7 D、 8 15.采用邻接表存储的图的深度优先遍历类似于二叉树的 。 A 先序 遍历 B 中序 遍历 C. 后序 遍历 D. 按层 遍历 二、填空题（本大题共 5 小题，每空 1 分，共 8 分；
10、答案填在下表内） 1 2 3 4 5 6 7 8 1.数据结构是研究数据元素 之间抽象化的相互关系和这种关系在计算机中的存储结构表示，根据数据元素之间关系的不同特性，通常有下列四类基本结构：集合、线性结构、 （ 1） 和 （ 2） 。 2.评价算法的标准很多，通常是以执行算法所需要的 （ 3） 和所占用的 （ 4） 来判别一个算法的优劣。 3.线性表的顺序存储结构特点是表中逻辑关系相邻的元素在机器内的 （ 5） 也是相邻的。 4.空格串的长度为串中所包含 （ 6） 字符的个数，空串的长度为 （ 7） 5.加上表示指向前驱和 （ 8） 的线索的二叉数称为线索二叉树。 三、判断题（对 的打“”，错
11、的打“”。每小题 1 分，共 10 分） （ ） 1.线性表的唯一存储形式是链表。 （ ） 2.已知指针 P 指向键表 L 中的某结点，执行语句 P=P- next 不会删除该链表中的结点。 （ ） 3.在链队列中，即使不设置尾指针也能进行入队操作。 （ ） 4.如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。 （ ） 5.设与一棵树 T 所对应的二叉树为 BT，则与 T 中的叶子结点所对应的 BT 中的结点也一定是叶子结点。 （ ） 6.快速排序是不稳定排序。 （ ） 7.任一 AOE 网中至少有一条关键路径，且是从源点到汇点 的路径中最短的一条。 （ ） 8.若图 G 的最小
12、生成树不唯一，则 G 的边数一定多于 n-1，并且权值最小的边有多条（其中 n 为 G 的顶点数）。 （ ） 9.给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。 （） 10.基数排序是多关键字排序。从最低位关键字起进行排序。 四、应用题。（共 44 分） 1.画出 该图的邻接矩阵 和邻接表。根据邻接表从 A 开始求 DFS 和 BFS 序列。 （ 12 分） 2.假设用于通信的电子由字符集 a,b,c,d,e,f,g,h中的字母构成，这 8 个字母在电文中出现的概率分别为 0.07， 0.19， 0.02， 0.06， 0.32， 0.03， 0.21， 0.10画出哈夫曼树，并
13、为这 8 个字母设计哈夫曼编码。（ 8 分） 3. 已知序列 70， 73， 69， 23， 93， 18,11， 68请给出直接插入排序作升序排序每一趟的结果和快速排序作升序排序时一趟的结果。 （ 10 分） 4.设有一组关键字 关键码集为 47， 7， 29， 11， 16， 92， 22， 8， 3，哈希表表长为 11， Hash(key)=key mod 11，用线性探测法处理冲突， 构造哈希表，并求它成功查找的 ASL。 （ 8分） 5. 二叉树的先序遍历序列 为 A B C D E F G H I，中序遍历序列为 B C A E D G H F I，画出这棵二叉树。 (6 分 )
14、五、算法设计题（ 8 分） 定义有序表抽象数据类型，并据此类型设计折半查找算法。 2012 年数据结构期末考试题及答案 一、选择题 1在数据结构中，从逻辑上可以把数据结构分为 C 。 A动态结构和静态结构 B紧凑结构和非紧凑结构 C线性结构和非线性结构 D内部结构和外部结构 2数据结构在计算机内存中的表 示是指 A 。 A数据的存储结构 B数据结构 C数据的逻辑结构 D数据元素之间的关系 3在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A逻辑 B存储 C逻辑和存储 D物理 4在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。 A数据的处理方法 B数据元素的类型 C数据元素之间的关系 D数据的存储方法 5在决定选取何种存储结构时，一般不考虑 A 。
