2004年10月全国自考数据结构试题
课程代码：(02331)
一、单项选择题(本大题共15小题，每小题2分，共30分)
1．下列各式中，按增长率由小至大的顺序正确排列的是(D)
A．，n！，2n ，n3/2                        B．n3/2，2n，nlogn，2100
C．2n，log n，nlogn，n3/2                    D．2100，logn, 2n, nn
2．若要在单链表中的结点*p之后插入一个结点*s，则应执行的语句是(A)
A．s->next=p->next; p->next=s;                B．p->next=s; s->next=p->next;
C．p->next=s->next; s->next=p;                D．s->next=p; p->next=s->next;
3．若要在O（1）的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向(B)
A．各自的头结点                            B．各自的尾结点
C．各自的第一个元素结点                    D．一个表的头结点，另一个表的尾结点
4．栈的两种常用存储结构分别为(A)
A．顺序存储结构和链式存储结构            B．顺序存储结构和散列存储结构
C．链式存储结构和索引存储结构            D．链式存储结构和散列存储结构
5．已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为(C)
A．5                B．6                C．16                D．17
6．已知在如下定义的链串结点中，每个字符占1个字节，指针占4个字节，则该链串的存储密度为(C)
typedef struct node{
char data[8];
struct node *next;
}LinkStrNode;
A．1/4                B．1/2                C．2/3                D．3/4
7．应用简单的匹配算法对主串s=″BDBABDABDAB″与子串t=″BDA″进行模式匹配，在匹配成功时，进行的字符比较总次数为(C)
A．7                B．9                C．10                D．12
8．二维数组A[20][10]采用列优先的存储方法，若每个元素占2个存储单元，且第1个元素的首地址为200，则元素A[8][9]的存储地址为(B)
A．574                B．576                C．578                D．580
9．对广义表L=((a,b),c,d)进行操作tail(head(L))的结果是(D)
A．（c,d）            B．(d)                C．b                D．(b)
10．已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为(D)
A．ABCDEF            B．ABCEFD            C．ABFCDE            D．ABCDFE
11．一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为(A)
A．O(n)                B．O(e)                C．O(n+e)            D．O(n2)
12．在关键字序列(12，23，34，45，56，67，78，89，91)中二分查关键字为45、89和12的结点时，所需进行的比较次数分别为(B)
A．4，4，3                                B．4，3，3
C．3，4，4                                D．3，3，4
13．下列排序方法中，最好与最坏时间复杂度不相同的排序方法是(A)
A．冒泡排序                                B．直接选择排序
C．堆排序                                D．归并排序
14．已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查成功的平均查长度等于(B)
A．1.0                                    B．2.9
C．3.4                                    D．5.5
15．在下列各种文件中，不能进行顺序查的文件是(C)
A．顺序文件                                B．索引文件
C．散列文件                                D．多重表文件
二、填空题(本大题共10小题，每小题2分，共20分)
16．抽象数据类型是指数据逻辑结构及与之相关的（操作）。
17．已知在结点个数大于1的单循环链表中，指针p指向表中某个结点，则下列程序段执行结束时，指针q指向结点*p的（前驱）结点。
q=p;
while(q->next!=p)q=q->next;
18．假设S和X分别表示进栈和出栈操作，由输入序列“ABC”得到输出序列“BCA”的操作序列为SSXSXX，则由“a*b+c/d”得到“ab*cd/+”的操作序列为（SXSSXXSSXSSXXX）。
19．在文本编辑程序中查某一特定单词在文本中出现的位置，可以利用串的（子串定位）运算。
20．假设以行优先顺序将一个n阶的5对角矩阵压缩存储到一维数组Q中，则数组Q的大小至少为（5n-6）。
21．在含100个结点的完全二叉树中，叶子结点的个数为（50）。
22．在无向图中，若从顶点a到顶点b存在（路径），则称a与b之间是连通的。
23．如果排序过程不改变（关键字相同的记录）之间的相对次序，则称该排序方法是稳定的。
24．索引顺序查适宜对（分块有序或有序）的顺序表进行查。
25．文件的检索操作可按检索条件不同分为下列四种询问，它们是简单询问、范围询问、函数询问及（布尔询问）。
三、解答题(本大题共4小题，每小题5分，共20分)
26．画出下图所示二叉树的中序线索链表的存储表示。
27．已知图G=（V，E），其中：
V={a,b,c,d,e},E={(a,b),(b,d),(c,b),(c,d),(d,e),(e,a),(e,c)}。
（1）画出图G；                （2）画出图G的邻接表。
答：(1) (2)
28．已知自顶向下的二路归并排序的算法如下所示，按此算法对关键字序列（55，28，73，91，37，64，19，82，46）进行排序，列出算法执行过程中前5次调用Merge函数进行归并之后的关键字序列。
void MergeSorDC(SeqList R, int low, int high){
// 用分治法对R[low..high]进行二路归并排序
int mid;
    if(low<high){                        //区间长度大于1
        mid=(low+high)/2;                //分解
        MergeSortDC(R, low, mid);        //递归地对id]排序
        MergeSortDC(R,mid+1,high);        //递归地对R[mid+1..high]排序
        Merge(R, low, mid, high);        //组合，将两个有序区归并为一个有序区
      }
}    //MergeSortDC
答：
第1次调用Merge进行归并之后的关键子序列为:(28,55,73,91,37,64,19,82,46)
第2次调用Merge进行归并之后的关键子序列为:(28,55,73,91,37,64,19,82,46)
第3次调用Merge进行归并之后的关键子序列为: (28,55,73,91,37,64,19,82,46)
第4次调用Merge进行归并之后的关键子序列为merge函数: (28,37,55,73,91,64,19,82,46)
第5次调用Merge进行归并之后的关键子序列为: (28,55,73,91,37,64,19,82,46)
29．由于元素的插入先后次序不同，所构成的二叉排序树可能有多种形态。请画出4棵含1，2，3，4，5，6六个元素且以1为根、深度为4的二叉排序树。
答：           
四、算法阅读题(本大题共4小题，每小题5分，共20分)
30．L为一个带头结点的循环链表。函数f30的功能是删除L中数据域data的值大于c的所有结点，并由这些结点组建成一个新的带头结点的循环链表，其头指针作为函数的返回值。请在空缺处填入合适的内容，使其成为一个完整的算法。
LinkList f30(LinkList L, int c){
LinkList Lc,p,pre;
      pre=L;
    p= (1);
    Lc=(LinkList)malloc(sizeof(ListNode));
      Lc->next=Lc;
      while(p!=L)
if(p->data>c){
        pre->next=p->next;
        (2);
        Lc->next=p;
        p=pre->next;
}
else{
    pre=p;
    (3);
}
      return Lc;
}
答：(1)L->next        (2)p->next=Lc->next        (3)p=p->net
31．设栈S=(1,2,3,4,5,6,7),其中7为栈顶元素。
（1）写出调用f31(&S)后的S；    （2）简述函数f31中第1个循环语句的功能。