《自考数据结构试题加答案2008年》由会员分享，可在线阅读，更多相关《自考数据结构试题加答案2008年（11页珍藏版）》请在金锄头文库上搜索。
1、 1 / 112008 年 1 月 一、单项选择题（本大题共 15 小题,每小题 2 分,共 30 分）在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。1.逻辑上通常可以将数据结构分为（C） P3A.动态结构和静态结构 B.顺序结构和链式结构 C.线性结构和非线性结构 D.初等结构和组合结构2.在下列对顺序表进行的操作中,算法时间复杂度为 O(1)的是（A）P16A.访问第 i 个元素的前驱（1next= =NULL C.head!=NULL D.headnext= =head4.已知栈的最大容量为 4。若进栈序列为 1,2,3,4,5
2、,6,且进栈和出栈可以穿插进行,则可能出现的出栈序列为（C）A.5,4,3,2,1,6 B.2,3,5,6,1,4 C.3,2,5,4,1,6 D.1,4,6,5,2,35.与线性表相比,串的插入和删除操作的特点是（D）P54A.通常以串整体作为操作对象 B.需要更多的辅助空间 C.算法的时间复杂度较高 D.涉及移动的元素更多6.假设以三元组表表示稀疏矩阵,则与如图所示三元组表对应的 45 的稀疏矩阵是（注：矩阵的行列下标均从 1 开始）（B）P64A. B.0450768 00453768C. D.04573068 003457687.以下有关广义表的表述中,正确的是（A）P66A.由 0
3、个或多个原子或子表构成的有限序列 B.至少有一个元素是子表C.不能递归定义 D.不能为空表8.树的先根序列等同于与该树对应的二叉树的（A）A.先序序列 B.中序序列 C.后序序列 D.层序序列9.假设有向图含 n 个顶点及 e 条弧,则表示该图的邻接表中包含的弧结点个数为（B）P105A.n B.e C.2e D.ne10.如图所示的有向无环图可以得到的不同拓扑序列的个数为（C）A.1 B.2 C.3 D.411.下列排序方法中,稳定的排序方法为（D）P139A.希尔排序 B.堆排序 C.快速排序 D.直接插入排序 2 / 1112.对下列关键字序列进行快速排序时,所需进行比较次数最少的是（C
4、）P147A.（1,2,3,4,5,6,7,8） B.（8,7,6,5,4,3,2,1）C.（4,3,8,6,1,7,5,2） D.（2,1,5,4,3,6,7,8）13.含 n 个关键字的二叉排序树的平均查找长度主要取决于（B）P180A.关键字的个数 B.树的形态 C.关键字的取值范围 D.关键字的数据类型14.下列查找算法中,平均查找长度与元素个数 n 不直接相关的查找方法是（D）P202A.分块查找 B.顺序查找 C.二分查找 D.散列查找15.可有效提高次关键字查找效率的文件是（B）P219A.顺序文件 B.倒排文件 C.散列文件 D.VSAM 文件二、填空题（本大题共 10 小题,
5、每小题 2 分,共 20 分）请在每小题的空格中填上正确答案。错填、不填均无分。16.数据的存储结构是其逻辑结构 映象 。P117.输入线性表的 n 个元素建立带头结点的单链表,其时间复杂度为 O（n） 。P2218.假设循环队列的元素存储空间大小为 m,队头指针 f 指向队头元素,队尾指针 r 指向队尾元素的下一个位置,则在少用一个元素空间的前提下,表示“队满”的条件是 (r+1)%m=f 。P3819.给定串的联接操作函数：char *strcat(char *to, char *from);/将串 from 联接到串 to 的末尾,并返回联接后的串若字符串 s1= point,s2= o
6、f,则 strcat(s1,strcat)(s2,s1)的操作结果是 Point of point 。20.假设二维数组 A810按行优先顺序存储,若每个元素占 2 个存储单元,元素 A00的存储地址为 100,则元素A45的存储地址为 190 。=100+（4*10+5）*221.假设一棵完全二叉树含 1000 个结点,则其中度为 2 的结点数为 498 。22.已知一个有向网如图所示,从顶点 1 到顶点 4 的最短路径长度为 55 。23.在快速排序、堆排序和归并排序中,最坏时间复杂度为 O(n2)的排序算法有 快速排序 。P15624.假设散列表的表长为 11,散列函数为 H(key)=
7、key%7,若用线性探测处理冲突,则探查地址序列 hi 的计算公式为Hi=( H(key)+i)%11 i=0,1,.10 。)10,2(i25.VSAM 文件由 索引集、顺序集 和数据集三部分组成。P215三、解答题（本大题共 4 小题,每小题 5 分,共 20 分）26.已知广义表的图形表示如图所示,(1)写出该广义表 L; (e),(),(a,(b,c,d),(b,c,d)(2)分别写出该广义表的深度和长度。 3,4 27.已知二叉树的先序序列和中序序列分别为 ABDEHCFI 和 DBHEACIF,(1)画出该二叉树的二叉链表存储表示;(2)写出该二叉树的后序序列。 DHEBIFCA
8、(154 60,15234 55,1234 60,前 9 层完整 2 9-1=511第 10 层 489 个n0+n1+n2=1000n1=1n0=n2+1 3 / 1128.已知有向图的邻接表如图所示,(1)写出从顶点 A 出发,对该图进行广度优先搜索遍历的顶点序列; ABDCE (2)画出该有向图的逆邻接表。29.依次读入给定的整数序列7,16,4,8,20,9,6,18,5,完成下列操作：1)构造一棵二叉排序树,计算在等概率情况下该二叉排序树的平均查找长度 ASL;2)若变更序列中元素的排列,可构造出平均查找长度达到最小的二叉排序树。写出满足上述要求的序列中的第一个元素。(1) ASL=
9、（1+2*2+3*4+4*2）/9=25/9(2) 7,16,4,8,20,9,6,18,54,5,6,7,8,9,16,18,20四、算法阅读题（本大题共 4 小题,每小题 5 分,共 20 分）30.假设以带头结点的单链表表示线性表,阅读下列算法 f30,并回答问题: (1)设线性表为( a 1, a2, a3, a4, a5, a6, a7 ), 写出执行算法 f30 后的线性表； (1) a 2, a4, a6(2)简述算法 f30 的功能。(2)删除编号为奇数的节点void f30(LinkList L)/L 为带头结点单链表的头指针LinkList p,q;P =L;while (
10、p &pnext)q = pnext;pnext =qnext;p =qnext;free(q);31.算法 f31 的功能是借助栈结构实现整数从 10 进制到 8 进制的转换,阅读算法并回答问题：(1)画出 n 为十进制的 1348 时算法执行过程中栈的动态变化情况;(2)说明算法中 while 循环完成的操作。void f31(int n) /n 为非负的十进制整数 4 / 11int e;SeqStack S;InitStack(& S);do Push(& S,n%8);n =n/8;while (n);while ( ! StackEmpty(& S)e =Pop(& S);prin
11、tf (%ld,e);(1)右图(2) 将栈中的数依次输出32.已知以二叉链表作二叉树的存储结构,阅读算法 f32,并回答问题：(1)设二叉树 T 如图所示,写出执行 f32(T)的返回值; 4 (2)简述算法 f32 的功能。 求二叉树 T 的深度int f32(BinTree T)int m, n;if(! T)return 0;elsem= f32(Tlchild);n = f 32(Trchild);if(mn)return m +1;else return n+1;33.设有向图邻接表定义如下；typedef structVertexNode adjlistMax VertexNum
12、;int n,e; /图的当前顶点数和弧数 ALGraph; /邻接表类型其中顶点表结点 VertexNode 结构为：边表结点 EdegNode 结构为： vertex firstedgeadjvex next 5 / 11阅读下列算法 f33,并回答问题：(1)已知有向图 G 的邻接表如图所示,写出算法 f33 的输出结果; (2)简述算法 f33 的功能。void dfs (ALGraph *G,int v)EdgeNode * p;visitedv=TRUE;printf(%c,Gadjlistv vertex);for(p =Gadjlistv)firstedge; p; p=pne
13、xt)if(! visitedpadjvex)dfs (G, padjvex); void f33(ALGraph *G)int v,w;for(v=0; v n; v +) for(w=0;wn; w+)visitedw=FALSE;printf(%d: ,v);dfs(G,v);printf(n); (1) ABCED(2) 深度优先搜索有向图五、算法设计题(本大题 10 分)34.假设以单链表表示线性表,单链表的类型定义如下:typedef struct node DataType data;struct node *next; LinkNode, *LinkList;编写算法,将一个头
14、指针为 head 且不带头结点的单链表改造为一个含头结点且头指针仍为 head 的单向循环链表,并分析算法的时间复杂度。LinkList ModifyList(head)LinkNode p;p=(LinkList)malloc(sizeof(LinkNode);p-next=head;head=p; 6 / 11while(p-next) p=p-nextp-next=head;2008 年 10 月 数据结构一、单项选择题(本大题共 15 小题,每小题 2 分,共 30 分)在每小题列出的四个备选项中只有一个是最符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。1.如果
15、在数据结构中每个数据元素只可能有一个直接前驱,但可以有多个直接后继,则该结构是（ C ）A. 栈 B. 队列 C. 树 D. 图2.下面程序段的时间复杂度为（ C ）for (i=0; inext=head B. p-next-next=headC. p-next=NULL D. p=head4.若以 S 和 X 分别表示进栈和退栈操作,则对初始状态为空的栈可以进行的栈操作系列是（ D ）A. SXSSXXXX B. SXXSXSSX C. SXSXXSSX D. SSSXXSXX5.两个字符串相等的条件是（ D ）A. 串的长度相等 B. 含有相同的字符集 C. 都是非空串 D. 串的长度相等且对应的字符相同6.如果将矩阵 Ann的每一列看成一个子表,整个矩阵看成是一个广义表 L,即 L=(a11,a21,an1),( a12,a22,an2),（a 1n,a2n,ann）),并且可以通过求表头 head 和求表尾 tail 的运算求取矩阵中的每一个元素,则求得 a21的运算是（ A ）A. head (tail (head (L) B. head (head(he
