1 / 7 2004 年 10 月全国自考数据结构试题 课程代码：(02331) 一、单项选择题(本大题共 15 小题，每小题 2 分，共 30 分) 1．下列各式中，按增长率由小至大的顺序正确排列的是(D) A．n ， 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) 2 / 7 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，...
