自考数据结构试题加答案2008年.doc

2008年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,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.C.D.7.以下有关广义表的表述中,正确的是（A）P66A.由0个或多个原子或子表构成的有限序列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.直接插入排序12.对下列关键字序列进行快速排序时,所需进行比较次数最少的是（C）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小题,每小题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=of,则strcat(s1,strcat)(s2,s1)的操作结果是 Point of point 。(154 60,15234 55,1234 60,前9层完整 29-1=511第10层489个n0+n1+n2=1000n1=1n0=n2+120.假设二维数组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)=key%7,若用线性探测处理冲突,则探查地址序列hi的计算公式为Hi=( H(key)+i)%11 i=0,1,.10 。25.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 28.已知有向图的邻接表如图所示,(1) 写出从顶点A出发,对该图进行广度优先搜索遍历的顶点序列; ABDCE (2) 画出该有向图的逆邻接表。29.依次读入给定的整数序列7,16,4,8,20,9,6,18,5,完成下列操作：1)构造一棵二叉排序树,计算在等概率情况下该二叉排序树的平均查找长度ASL; 2)若变更序列中元素的排列,可构造出平均查找长度达到最小的二叉排序树。写出满足上述要求的序列中的第一个元素。(1) ASL=（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) 设线性表为( a1, a2, a3, a4, a5, a6, a7 ), 写出执行算法f30后的线性表； (1) a2, a4, a6(2) 简述算法f30的功能。(2)删除编号为奇数的节点 void f30(LinkList L)/L为带头结点单链表的头指针LinkList p,q;P =L;while (p &pnext)q = pnext;pnext =qnext;p =qnext;free(q); 31.算法f31的功能是借助栈结构实现整数从10进制到8进制的转换,阅读算法并回答问题：(1) 画出n为十进制的1348时算法执行过程中栈的动态变化情况;(2) 说明算法中while循环完成的操作。void f31(int n) /n为非负的十进制整数 int e; SeqStack S; InitStack(& S); do Push(& S,n%8);n =n/8;while (n);while ( ! StackEmpty(& S)e =Pop(& S);printf (%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; else m= f32(Tlchild); n = f 32(Trchild); if(mn)return m +1; else return n+1; 33.设有向图邻接表定义如下； typedef struct VertexNode adjlistMax VertexNum; int n,e; /图的当前顶点数和弧数 ALGraph; /邻接表类型vertexfirstedge其中顶点表结点VertexNode结构为：adjvexnext边表结点EdegNode结构为： 阅读下列算法f33,并回答问题：(1)已知有向图G的邻接表如图所示,写出算法f33的输出结果; (2)简述算法f33的功能。void dfs (ALGraph *G,int v) EdgeNode * p; visitedv=TRUE; printf(%c,Gadjlistvvertex); for(p =Gadjlistv)firstedge; p; p=pnext) 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; 编写算法,将一个头指针为head且不带头结点的单链表改造为一个含头结点且头指针仍为head的单向循环链表,并分析算法的时间复杂度。LinkList ModifyList(head) LinkNode p;p=(LinkList)malloc(sizeof(LinkNode);p-next=head;head=p;while(p-next) p=p-nextp-next=head;2008年10月 数据结构一、单项选择题(本大题共15小题,每小题2分,共30分)在每小题列出的四个备选项中只有一个是最符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。1.如果在数据结构中每个数据元素只可能有一个直接前驱,但可以有多个直接后继,则该结构是（ C ）A. 栈 B. 队列 C. 树 D. 图2.下面程序段的时间复杂度为（ C ）for (i=0; im; i+)for (j=0; jnext=headB. p-next-next=headC. p-next=NULLD. p=head4.若以S和X分别表示进栈和退栈操作,则对初始状态为空的栈可以进行的栈操作系列是（ D ）A. SXSSXXXX B. SXXSXSSX C. SXSXXSSXD. SSSXXSXX5.两个字符串相等的条件是（ D ）A. 串的长度相等 B. 含有相同的字符集 C. 都是非空串D. 串的长度相等且对应的字符相同6.如果将矩阵Ann的每一列看成一个子表,整个矩阵看成是一个广义表L,即L=(a11,a21,an1),( a12,a22,an2),（a1n,a2n,ann）),并且可以通过求表头head和求表尾tail的运算求取矩阵中的每一个元素,则求得a21的运算是（ A ）A. head (tail (head (L)B. head (head(head(L)C. tail (head (tail (L)D. head (head (tail (L)7.已知一棵含50个结点的二叉树中只有一个叶子结点,则该树中度为1的结点个数为（ D ）A. 0 B. 1 C. 48 D. 498.在一个具有n个顶点的有向图中,所有顶点的出度之和为Dout ,则所有顶点的入度之和为（ A ）A. Dout B. Dout-1 C. Dout+1 D. n9.如图所示的有向无环图可以得到的拓扑序列的个数是（ C ）A. 3 B. 4 C. 5 D. 626534 26354 25634 62534 6523410.如图所示的带权无向图的最小生成树的权为（ C ）A. 51 B. 52 C. 54 D. 5611.对长度为n的关键字序列进行堆排序的空间复杂度为（ B ）A. O（log2n） B. O（1） C. O（n） D. O（n*log2n）12.已知用某种排序方法对关键字序列（51,35,93,24,13,68,56,42,77）进行排序时,前两趟排序的结果为（35,51,24,13,68,56,42,77,93）（35,24,13,51,56,42,68,77,93）所采用的排序方法是（ B ）A. 插入排序 B. 冒泡排序 C. 快速排序 D. 归并排序13.已知散列表的存储空间为T0.18,散列函数H（key）=key%17,并用二次探测法处理冲突。散列表中已插入下列关键字：T5=39,T6=57和T7=7,则下一个关键字23插入的位置是（ D ）A. T2 B. T4 C. T8 D. T1014.适宜进行批量处理的文件类型是（ A ）A. 顺序文件 B. 索引顺序文件 C. 散列文件 D. 多关键字文件15.VSAM文件的索引结构为（ A ）A. B+树 B. 二叉排序树 C. B-树 D. 最优二叉树二、填空题(本大题共10小题,每小题2分,共20分)请在每小题的空格中填上正确答案。错填、不填均无分。16.如果某算法对于规模为n的问题的时间耗费为T（n）=3n3,在一台计算机上运行时间为t秒,则在另一台运行速度是其64倍的机器上,用同样的时间能解决的问题规模是原问题规模的 4 倍。17.将两个长度分别为m和n的递增有序单链表,归并成一个按元素递减有序的单链表,可能达到的最好的时间复杂度是 O（m+n） 。18.已知循环队列的存储空间大小为m,队头指针front指向队头元素,队尾指针rear指向队尾元素的下一个位置,则在队列不满的情况下,队列的长度是 （rear-front+m）%m 。19.字符串“sgabacbadfgbacst” 中存在有 3 个与字符串“ba”相同的子串。20.假设以列优先顺序存储二维数组A58,其中元素A00的存储地址为LOC（a00）,且每个元素占4个存储单元,则数组元素Aij的存储地址为 LOC（a00）+4（5j+i） 。21.假设用表示树的边（其中x是y的双亲）,已知一棵树的边集为,该树的度是 3 。22.n个顶点且含有环路的无向连通图中,至少含有 n 条边。23.在一般情况下用直接插入排序、选择排序和冒泡排序的过程中,所需记录交换次数最少的是 选择排序 。24.和二分查找相比,顺序查找的优点是除了不要求表中数据元素有序之外,对 存储 结构也无特殊要求。25.顺序文件中记录存放的物理顺序和 逻辑 顺序一致。三、解答题(本大题共4小题,每小题5分,共20分)26.由森林转换得到的对应二叉树如图所示,写出原森林中第三棵树的前序序列和后序序列。前序序列：G H I J（2分）后序序列：H J I G（3分）27.图的邻接表的类型定义如下所示：#define MaxVertexNum 50typedef struct node int adjvex;struct node *next;EdgeNode;typedef struct VertexType vertex;EdgeNode *firstedge;VertexNode;题27图typedef VertexNode AdjListMaxVertexNum;typedef struct AdjList adjlist;int n, e;ALGraph;为便于删除和插入图的顶点的操作,可将邻接表的表头向量定义为链式结构,两种定义的存储表示实例如下图所示,请写出重新定义的类型说明。28.某类物品的编号由一个大写英文字母及2位数字（0.9）组成,形如E32。运用基数排序对下列物品编号序列进行按字典序的排序,写出每一趟（分配和收集）后的结果。E13,A37,F43,B32,B47,E12,F37,B12第一趟：B32，E12，B12，E13，F43，A37，B47，F37（2分）第二趟：E12，B12，E13，B32，A37，F37，F43，B47（2分）第三趟：A37，B12，B32，B47，E12，E13，F37，F43（1分）29.（1）画出对表长为13的有序顺序表进行二分查找的判定树；（2）已知关键字序列为（12,14,16,21,24,28,35,43,52,67,71,84,99）,写出在该序列中二分查找37时所需进行的比较次数。（1）如图（2）3次四、算法阅读题（本大题共4小题,每小题5分,共20分）30.已知线性表的存储结构为顺序表,阅读下列算法,并回答问题：（1）设线性表L=（21,-7,-8,19,0,-11,34,30,-10）,写出执行f30(&L)后的L状态；（2）简述算法f30的功能。void f30 (SeqList *L) int i,j;for (i=j=0;ilength; i+)if(L-datai=0)if(i!=j)L-dataj=L-datai;j+；L-length=j;（1）L=（21，19，0，34，30）（2分）（2）删除顺序表中的负值元素。（3分）31.阅读下列算法,并回答问题：（1）Q、Q1和Q2都是队列结构,设队列Q=（1,0,-5,2,-4,-6,9）,其中1为队头元素,写出执行f31 (&Q,&Q1,&Q2)之后队列Q、Q1和Q2的状态；（2）简述算法f31的功能。（注：lnitQueue、EnQueue、DeQueue和QueueEmpty分别是队列初始化、入列、出队和判队空的操作）void f31 (Queue*Q, Queue*Q1, Queue*Q2) int e;lnitQueue (Q1);lnitQueue (Q2);while (!QueueEmpty (Q) e=DeQueue (Q);if (e=0) EnQueue (Q1,e);else EnQueue (Q2,e)（1）Q=（）（1分） Q1=（1，0，2，9）（1分） Q2=（-5，-4，-6）（1分）（2）将队列Q的元素依次退队，并将正值及0元素入队到Q1，负值元素入队到Q2。（2分）32.阅读下列算法,并回答问题：（1）假设串由合法的英文字母和空格组成,并以0作结束符。设串s=”|amastudent”(表示空格符),写出f32（s）的返回值；（1）4（2分）（2）简述算法f32的功能。（2）对字符串内的单词个数进行累加计数。（3分）int f32 (char*s)int i, n, inword;n=inword=0;for (i=0;si!=0;i+)if (si!=& inword=0)inword=1;n+;else if (si=& inword=1)inword=0;return n;33.阅读下列对正整数关键字序列L操作的算法,并回答问题：（1）设L=(28,19,27,49,56,12,10,25,20,50),写出f33 (L,4)的返回值； 20 （2）简述函数f33的功能。利用快速排序的“划分”机制进行查找，以求取序列中排行第k小的元素。int Partition (SeqList*L, int low, int high);对Llow.high做划分,返回基准记录的位置,并使左部的关键字都小于或等于基准记录的关键字,右部的关键字都大于基准记录的关键字int f33 (SeqList L, int k)int low, high, pivotpos;low=1;high=L.length;if (khigh)return-1;do pivotpos=Partition (&L, low, high);调用快速排序的划分算法if (pivotposk)high=pivotpos-1;while (pivotpos!=k);return L.data pivotpos;五、算法设计题（本题10分）34.二叉排序树的类型定义如下：typedef struct BSTNode 二叉排序树的结点结构int data; 数据域struct BSTNode *lchild, *rchild; 左、右孩子指针BSTNode,*BSTree;设计递归算法,统计一棵二叉排序树T中值小于a的结点个数。 11 / 11