全国10月自学考试数据结构试题由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“全国自学考试试题”。
☆自考乐园---心境随缘，诚与天下自考人共勉！！
☆自考乐园---分享快乐，你的快乐老家！！☆自考乐园---引领成功，你的精神乐园！！自考乐园俱乐部，专注于自考，致力于成为全国最全，最优的自考学习交流，资料共享平台.....全国2009年10月自学考试数据结构试题
课程代码：02331
一、单项选择题（本大题共15小题，每小题2分，共30分）
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
1．按值可否分解，数据类型通常可分为两类，它们是（）A．静态类型和动态类型 C．原子类型和结构类型
B．原子类型和表类型 D．数组类型和指针类型
2．对于三个函数f(n)=2008n3+8n2+96000，g(n)=8n3+8n+2008和h(n)=8888nlogn+3n2，下列陈述中不成立的．是（）A．f(n)是0(g(n))C．h(n)是0(nlogn)
B．g(n)是0(f(n))D．h(n)是0(n2)3．指针p、q和r依次指向某循环链表中三个相邻的结点，交换结点*q和结点*r在表中次序的程序段是（）
A．p->next=r；
q->next=r->next；
r->next=q； B．p->next=r；
r->next=q；
q->next=r->next； C．r->next=q；
q->next=r->next；
p->next=r； D．r->next=q；
p->next=r；
q->next=r->next；
4．若进栈次序为a，b，c，且进栈和出栈可以穿插进行，则可能出现的含3个元素的出栈序列个数是（）A．3 C．6
B．5 D．7 5．假设以数组A［n］存放循环队列的元素，其头指针front指向队头元素的前一个位置、尾指针rear指向队尾元素所在的存储位置，则在少用一个元素空间的前提下，队列满的判定条件为（）A．rear= =front C．rear+1= =front 6．串的操作函数str定义为：
int str(char*s){ char *p=s；
while(*p！=′ ′)p++； return p-s； }俱乐部名称：自考乐园;俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id，可以直接进入俱乐部）；俱乐部url地址：http://tieba.baidu.com/club/5346389（您也可以通过此url进入俱乐部。）
B．(front+1)％n= =rear D．(rear+1)％n= =front
☆自考乐园---心境随缘，诚与天下自考人共勉！！
☆自考乐园---分享快乐，你的快乐老家！！☆自考乐园---引领成功，你的精神乐园！！自考乐园俱乐部，专注于自考，致力于成为全国最全，最优的自考学习交流，资料共享平台.....则str(″abcde″)的返回值是（）A．3 C．5
B．4 D．6 7．二维数组A［10］［6］采用行优先的存储方法，若每个元素占4个存储单元，已知元素A［3］［4］的存储地址为1000，则元素A［4］［3］的存储地址为（）A．1020 C．1036
B．1024 D．1240 8．对广义表L=(a，())执行操作tail(L)的结果是（）A．()C．a
B．(())D．(a)9．已知二叉树的中序序列和后序序列均为ABCDEF，则该二叉树的先序序列为（）A．FEDCBA C．FDECBA
B．ABCDEF D．FBDCEA 10．已知森林F={T1，T2，T3，T4，T5}，各棵树Ti(i=1，2，3，4，5)中所含结点的个数分别为7，3，5，l，2，则与F对应的二叉树的右子树中的结点个数为（）A．2 C．8
B．3 D．11 11．若非连通无向图G含有21条边，则G的顶点个数至少为（）．A．7 C．21
B．8 D．22 12．如图所示的有向图的拓扑序列是（）A．c，d，b，a，e B．c，a，d，b，e C．c，d，e，a，b D．c，a，b，d，e 13．对关键字序列(6，1，4，3，7，2，8，5)进行快速排序时，以第1个元素为基准的一次划分的结果为（）
A．(5，1，4，3，6，2，8，7)C．(5，1，4，3，2，6，8，7)
B．(5，1，4，3，2，6，7，8)D．(8，7，6，5，4，3，2，1)14．分块查找方法将表分为多块，并要求（）A．块内有序 C．各块等长
B．块间有序 D．链式存储
15．便于进行布尔查询的文件组织方式是（）A．顺序文件 C．散列文件
B．索引文件 D．多关键字文件俱乐部名称：自考乐园;俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id，可以直接进入俱乐部）；俱乐部url地址：http://tieba.baidu.com/club/5346389（您也可以通过此url进入俱乐部。）
☆自考乐园---心境随缘，诚与天下自考人共勉！！
☆自考乐园---分享快乐，你的快乐老家！！☆自考乐园---引领成功，你的精神乐园！！自考乐园俱乐部，专注于自考，致力于成为全国最全，最优的自考学习交流，资料共享平台.....二、填空题（本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分）
请在每个空格中填上正确答案。错填、不填均无分。
16．数据的链式存储结构的特点是借助________表示数据元素之间的逻辑关系。17．如果需要对线性表频繁进行________或________操作，则不宜采用顺序存储结构。18．如图所示，可以利用一个向量空间同时实现两个类型相为空的条件是top1=0，栈2为空的条件是top2=n-1，则件是________。
19．静态存储分配的顺序串在进行插入、置换和________等操作时可能发生越界。20．广义表L=（a，（b，()））的深度为________。
21．任意一棵完全二叉树中，度为1的结点数最多为________。
22．求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中________的数目正相关。
23．在5阶B-树中，每个结点至多含4个关键字，除根结点之外，其他结点至少含________个关键字。24．若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是________的。25．常用的索引顺序文件是________文件和________文件。
三、解答题(本大题共4小题，每小题5分，共20分)26．如图所示，在n×n矩阵A中，所有下标值满足关系式i+j＜n+l的元素aij的值均为0，现将A中其它元素按行优先顺序依次存储到长度为n(n+1)/2的一维数组sa中，其中元素a1，n存储在sa［0］。(1)设n=10，元素a4，9存储在sa［p］，写出下标p的值；
(2)设元素ai，j存储在sa［k］中，写出由i,j和n计算k的一般公式。
同的栈。其中栈1“栈满”的判定条
27．由字符集{s，t，a，e，I}及其在电文中出现的频度构建的哈夫曼树如图所示。已知某段电文的哈夫曼编码为111000010100，请根据该哈夫曼树进行译码，写出原来的电文。
28．已知无向图G的邻接表如图所示，俱乐部名称：自考乐园;俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id，可以直接进入俱乐部）；俱乐部url地址：http://tieba.baidu.com/club/5346389（您也可以通过此url进入俱乐部。）
☆自考乐园---心境随缘，诚与天下自考人共勉！！
☆自考乐园---分享快乐，你的快乐老家！！☆自考乐园---引领成功，你的精神乐园！！自考乐园俱乐部，专注于自考，致力于成为全国最全，最优的自考学习交流，资料共享平台.....(1)画出该无向图；
(2)画出该图的广度优先生成森林。
29．对序列(48，37，63，96，22，31，50，55，11)进行升序的堆排序，写出构建的初始(大根)堆及前两趟重建堆之后的序列状态。初始堆： 第1趟： 第2趟：
四、算法阅读题(本大题共4小题，每小题5分，共20分)30．阅读下列算法，并回答问题：
(1)无向图G如图所示，写出算法 f30(&G)的返回值；(2)简述算法f30的功能。#define MaxNum 20 int visited[MaxNum]； void DFS(Graph *g，int i)；
/*从顶点vi出发进行深度优先搜索，访问顶点vj时置visited[j]为1*/ int f30(Graph *g){ int i，k；
for(i=0；
in；
i++)／*g->n为图g的顶点数目*／
visited[i]=0；俱乐部名称：自考乐园;俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id，可以直接进入俱乐部）；俱乐部url地址：http://tieba.baidu.com/club/5346389（您也可以通过此url进入俱乐部。）
☆自考乐园---心境随缘，诚与天下自考人共勉！！
☆自考乐园---分享快乐，你的快乐老家！！☆自考乐园---引领成功，你的精神乐园！！自考乐园俱乐部，专注于自考，致力于成为全国最全，最优的自考学习交流，资料共享平台.....for(i=k=0；
in;i++)if(visited[i]= =0){ k++； DFS(g，i)； } return k； }
31．假设学生成绩按学号增序存储在带头结点的单链表中，类型定义如下：
typedef struct Node { int id;
/*学号*/ int score；
/*成绩*/ struct Node
*next； } LNode，*LinkList； 阅读算法f31，并回答问题：(1)设结点结构为f31(A，B)后A所指的链表；，成绩链表A和B如图所示，画出执行算法
(2)简述算法f31的功能。
void f31(LinkList A, LinkList B){ LinkList p, q;p=A->next;q=B->next;while(p && q){ if(p->idid)p=p->next;else if(p->id>q->id)q=q->next;else { if(p->score
俱乐部名称：自考乐园;俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id，可以直接进入俱乐部）；俱乐部url地址：http://tieba.baidu.com/club/5346389（您也可以通过此url进入俱乐部。）
☆自考乐园---心境随缘，诚与天下自考人共勉！！
☆自考乐园---分享快乐，你的快乐老家！！☆自考乐园---引领成功，你的精神乐园！！自考乐园俱乐部，专注于自考，致力于成为全国最全，最优的自考学习交流，资料共享平台.....if(q->scorescore=q->score;else p->score=60;p=p->next;q=q->next;} } } 32．阅读下列算法，并回答问题：
(1)设串s=“OneWorldOneDream”，t=＂One＂，pos是一维整型数组，写出算法 f32(s，t，pos)执行之后得到的返回值和pos中的值；(2)简述算法f32的功能。
int strlen(char*s)；
/*返回串s的长度*/ int index(char*st，char*t)；
／*若串t在串st中出现，则返回在串st中首次出现的下标值，否则返回-1*/ int f32(char*s, char*t, int pos［］){ int i, j, k, ls, lt;ls=strlen(s);1t=strlen(t);if(ls= =0||1t= =0)return-1;k=0;i=0;do { j=index(s+i, t);if(j>=0){ pos［k++］=i+j;i+=j+1t;} }while(i+1t=0);return k;} 33．二叉排序树的存储结构定义为以下类型：
typedef int KeyType;typedef struct node { KeyType
key;
/*关键字项*/俱乐部名称：自考乐园;俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id，可以直接进入俱乐部）；俱乐部url地址：http://tieba.baidu.com/club/5346389（您也可以通过此url进入俱乐部。）
☆自考乐园---心境随缘，诚与天下自考人共勉！！
☆自考乐园---分享快乐，你的快乐老家！！☆自考乐园---引领成功，你的精神乐园！！自考乐园俱乐部，专注于自考，致力于成为全国最全，最优的自考学习交流，资料共享平台.....InfoType
otherinfo;
/*其它数据项*/ struct node *1child, *rchild;/*左、右孩子指针*/ } BSTNode, *BSTree； 阅读算法f33，并回答问题：
(1)对如图所示的二叉排序树T，写出f33(T，8)返回的指针所指结点的关键字；(2)在哪些情况下算法f33返回空指针?(3)简述算法f33的功能。
BSTNode *f33(BSTree T, KeyType x){
BSTNode
*p;if(T= =NULL)return NULL;p=f33(T->1child, x);if(p!=NULL)return p;if(T->key>x)return T;return f33(T-> rchild, x);}
五、算法设计题（本题10分）
34．假设线性表采用顺序存储结构，其类型定义如下：
#define ListSize 100 typedef struct { int data［ListSize］;int length;} SeqList, *Table;编写算法，将顺序表L中所有值为奇数的元素调整到表的前端。俱乐部名称：自考乐园;俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id，可以直接进入俱乐部）；俱乐部url地址：http://tieba.baidu.com/club/5346389（您也可以通过此url进入俱乐部。）
☆自考乐园---心境随缘，诚与天下自考人共勉！！
☆自考乐园---分享快乐，你的快乐老家！！☆自考乐园---引领成功，你的精神乐园！！自考乐园俱乐部，专注于自考，致力于成为全国最全，最优的自考学习交流，资料共享平台.....以上资料由百度贴吧：
----------自考乐园俱乐部杨尚杰为你精心编辑俱乐部名称：自考乐园;俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id，可以直接进入俱乐部）；俱乐部url地址：http://tieba.baidu.com/club/5346389（您也可以通过此url进入俱乐部。）
