月全国自考数据结构()试题附标准答案

《月全国自考数据结构()试题附标准答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2004年10月全国自考数据结构试题课程代码：(02331)一、单项选择题(本大题共15小题，每小题2分，共30分)1．下列各式中，按增长率由小至大的顺序正确排列的是(D)A．，n！，2n，n3/2B．n3/2，2n，nlogn，2100C．2n，logn，nlogn，n3/2D．2100，logn,2n,nn2．若要在单链表中的结点*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->nex

2、t=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．5B．

3、6C．16D．176．已知在如下定义的链串结点中，每个字符占1个字节，指针占4个字节，则该链串的存储密度为(C)typedefstructnode{chardata[8];structnode*next;}LinkStrNode;A．1/4B．1/2C．2/3D．3/47．应用简单的匹配算法对主串s=″BDBABDABDAB″与子串t=″BDA″进行模式匹配，在匹配成功时，进行的字符比较总次数为(C)彈贸摄尔霁毙攬砖卤庑。A．7B．9C．10D．128．二维数组A[20][10]采用列优先的存储方法，若每个元素占2个存储单元，且第1个元素的首地址为200，则元素A[8][9]的存储地

4、址为(B)謀荞抟箧飆鐸怼类蒋薔。8/8A．574B．576C．578D．5809．对广义表L=((a,b),c,d)进行操作tail(head(L))的结果是(D)A．（c,d）B．(d)C．bD．(b)10．已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为(D)厦礴恳蹒骈時盡继價骚。A．ABCDEFB．ABCEFDC．ABFCDED．ABCDFE11．一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为(A)茕桢广鳓鯡选块网羈泪。A．O(n)B．O(e)C．O(n+e)D．O(n2)12．在

5、关键字序列(12，23，34，45，56，67，78，89，91)中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为(B)鹅娅尽損鹌惨歷茏鴛賴。A．4，4，3B．4，3，3C．3，4，4D．3，3，413．下列排序方法中，最好与最坏时间复杂度不相同的排序方法是(A)A．冒泡排序B．直接选择排序C．堆排序D．归并排序14．已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于(B)籟丛妈羥为贍偾蛏练淨。A．1.0B．2.9C．3.4D．5.515．在下列各种文件中，不能进行顺序查找的文件是(C)A．顺序文件B．索引文件C．

6、散列文件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．在文本编辑程序中查找某一特

7、定单词在文本中出现的位置，可以利用串的（子串定位）运算.8/820．假设以行优先顺序将一个n阶的5对角矩阵压缩存储到一维数组Q中，则数组Q的大小至少为（5n-6）.铙誅卧泻噦圣骋贶頂廡。21．在含100个结点的完全二叉树中，叶子结点的个数为（50）.22．在无向图中，若从顶点a到顶点b存在（路径），则称a与b之间是连通的.23．如果排序过程不改变（关键字相同的记录）之间的相对次序，则称该排序方法是稳定的.24．索引顺序查找适宜对（分块有序或有序）的顺序表进