2013年1月自学考试数据结构试题

　 课程代码：02331

　　请考生按规定用笔将所有试题的答案涂、写在答题纸上。

　　选择题部分

　　注意事项：

　　1.答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。

　　2.每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。

　　一、单项选择题(本大题共15小题，每小题2分，共30分)

　　在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将答题

　　纸的相应代码涂黑。错涂、多涂或未涂均无分。

　　1.数据的逻辑结构可以分为

　　A.动态结构和静态结构 B.顺序结构和链式结构

　　C.线性结构和非线性结构 D.简单结构和构造结构

　　2.线性表是一个有限序列，组成线性表的基本单位是

　　A.数据项 B.数据元素

　　C.数据域 D.字符

　　3.栈中有a、b和c三个元素，a是栈底元素，c是栈顶元素，元素d等待进栈，则不可

　　能的出栈序列是

　　A.dcba B.cbda

　　C.cadb D.cdba

　　4.稀疏矩阵的三元组表是

　　A.顺序存储结构 B.链式存储结构

　　C.索引存储结构 D.散列表存储结构

　　5.已知广义表G，head(G)与tail(G)的深度均为6，则G的深度是

　　A.5 B.6

　　C.7 D.8

　　6.下列编码集合中，属于前缀编码的一组是

　　A.{11,10,001,101,0001} B.{00,010,0110,1000}

　　C.{11,01,001,0101,0001} D.{0,10,110,1011}

　　7.如题7图所示二叉树的中序序列为

　　A.ACDB

　　B.DCBA

　　C.CDBA

　　D.ABCD

　　题7图

　　8.有向图中所有顶点入度之和与所有顶点出度之和的比是

　　A.1/2 B.1

　　C.2 D.4

　　9.含有n个顶点和e条边的有向图的邻接矩阵中，零元素的个数是

　　A.e B.2e

　　C.n2-2e D.n2-e

　　10.n个顶点的无向连通图，其生成树的边数为

　　A.n-l B.n

　　C.n+l D.nlogn

　　11.用自底向上的冒泡排序方法对序列(8,13,26,55,29,44)从大到小排序，第一趟排序需进行交换的次数为

　　A.2 B.3

　　C.4 D.5

　　12.对序列(8,13,26,55,29,44)从小到大进行基数排序，第一趟排序的结果是

　　A.(13,44,55,26,8,29) B.(13,26,55,44,8,29)

　　C.(8,13,26,29,44,55) D.(29,26,8,44,55,13)

　　13.采用分块查找时，要求数据

　　A.块内有序 B.分块有序

　　C.分块无序 D.每块中数据个数必须相同

　　14.下列关于散列函数的说法正确的是

　　A.散列函数越复杂越好

　　B.散列函数越简单越好

　　C.用除余法构造的散列函数是最好的

　　D.在冲突尽可能少的情况下，散列函数越简单越好

　　15.下列关于m阶B树的叙述中，错误的是

　　A.每个结点至多有m棵子树

　　B.每个结点至多有m-1个关键字

　　C.所有的叶结点均在同一层上

　　D.根结点至少有 棵子树

　　非选择题部分

　　注意事项：

　　用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。

　　二、填空题(本大题共10小题，每小题2分，共20分)

　　16.算法的时间复杂度与实现时采用的程序设计语言____________。

　　17.在长度为n的顺序表的第i(1≤i≤n)个元素之后插入一个元素时，需向后移动___________个元素。，

　　18.设循环队列存放在向量data[0..m-l]中，在出队操作后，队头指针front变化为___________。

　　19.树的前序遍历序列等同于该树对应二叉树的____遍历序列。

　　20.一个100×90的整型稀疏矩阵有10个非零元素，设每个整型数占2个字节，则用三元组表存储该矩阵时，所需的字节数是___________。

　　21.当用二叉链表作为n个结点的二叉树的存储结构时，空指针域的个数是____。

　　22.采用邻接表表示n个顶点的有向图时，若表结点的个数为m，则该有向图的边数

　　为___________。

　　23.对同一个基本有序的待排序列分别进行堆排序、快速排序和冒泡排序，最省时间的

　　算法是___________。

　　24.在16个记录的有序顺序表中进行二分查找，最大比较次数是___________。

　　25.在排序算法中，若排序前后具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是___________的。

　　三、解答题(本大题共4小题，每小题5分，共20分)

　　26.在定义顺序表时，存放表结点的向量空间不宜过大也不宜过小，为什么?

　　27.画出题27图所示树的孩子链表。

　　题27图

　　28.已知一个无向图G如题28图所示，以顶点①为根，且小序号优先，分别画出G的深度优先生成树和广度优先生成树。

　　题28图

　　29.判别以下序列是否为堆，若不是，将其调整为大根堆，并画出大根堆。

　　①(1,5,7,20,18,8,10,40)

　　②(18,9,5,8,4,17,21,6)

　　四、算法阅读题(本大题共4小题，每小题5分，共20分)

　　30.单链表类型定义如下：

　　typedef struct node {

　　DataType data;

　　struct node next;

　　}ListNode;

　　typedef ListNode LinkList;

　　阅读下列算法，并回答问题：

　　void f30 (LinklList head, DataType x)

　　{ ∥head是带头结点的非空单链表的头指针

　　ListNode p， q;

　　p=head;

　　while(p->next->next)

　　p=p->next;

　　q=(ListNode) malloc (sizeof(ListNode));

　　q->data=x;

　　q->next=p->next;

　　p->next=q;

　　}

　　(1)该算法的功能是什么?

　　(2)若单链表的长度为n，算法的时间复杂度是多少?该时间复杂度和链表的初始状态有关吗?

　　31.阅读下列算法(假设栈的操作函数都已定义)，并回答问题：

　　void f31 ( )

　　{ SeqStack S;

　　char x， y;

　　x=′c′;

　　y=′k′;

　　Push (&S，x);

　　Push (&S，′a′);

　　Push (&S，y);

　　x=Pop(&S);

　　Push(&S，′t′);

　　Push(&S，x);

　　x=Pop(&S);

　　Push(&S，′s′);

　　while ( !StackEmpty(&S))

　　{ y=Pop (&S);

　　putchar (y);

　　}

　　putchar (x);

　　}

　　(1)自底向上写出执行while语句之前栈S中的元素序列。

　　(2)写出该函数的最后输出结果。

　　32.下列算法的功能是在中序线索树中查找结点p的前趋，填上适当内容使算法完整。

　　typedef enum { Link,Thread } PointerTag;

　　∥ 枚举值Link和Thread分别为0和1

　　typedef struct node {

　　DataType data;

　　PointerTag ltag, rtag;

　　Struct node lchild, rchild;

　　}BinThrNode;

　　BinThrNodef32 (BinThrNode p)

　　{ ∥ 在中序线索树中找结点p的中序前趋，设p非空

　　BinThrNode q;

　　if(p->ltag==Thread) (1) ;

　　else

　　{

　　q=p->lchild;

　　while(q->rtag=Link) (2) ;

　　return q;

　　}

　　}

　　33.分析下列排序算法中语句1和语句2的频度以及此算法的时间复杂度，并指出该算法是属于哪一种排序方法。

　　void f33( int a[ ],int n )

　　{ int i，j，k，t;

　　for (i=0;i

　　{ j=i;

　　for (k=j+1;k<=n;k++)

　　if (a[k]

　　t=a[i]; a[i]=a[j];a[j]=t;

　　}

　　}

　　五、算法设计题(本题10分)

　　34.二叉排序树的类型定义如下：

　　typedef struct node {

　　int data;

　　struct node lchild,rchild;

　　}BSTree;

　　编写递归算法从小到大输出二叉排序树T中所有data域值大于m且小于n的数据。

　　函数原型为void f34(BSTree T， int m， int n)