2331数据结构.doc

高等教育自学考试数据结构 复习题（课程代码 02331）一、单项选择题1算法能正确的实现预定功能的特征称为算法的 【 】 A正确性B易读性C健壮D高效率2下列时间复杂度中最坏的是 【 】AO(1)BO(2n)CO(lgn)DO()3在计算机中存储一个数据元素的位串称为 【 】A结点B数据项C数据域D字符串4在一个单链表中，若P所指结点不是最后结点，删除P之后的结点，则执行 【 】Ap next = p next nextBp = p nextCp = p next nextDp next = p5线性表L，经过运算InitList(L)后，函数Empty(L)的值是 【 】A1BfalseC0 Dnull6在双向链表中，一个结点含有的指针个数为 【 】A1B2C0 D37指针p指向单向循环链表L的首元素的条件是 【 】Ap = = LBp next = = LCL next = = p Dp next = = NULL8经过下列栈的运算后x的值是InitStack(s); Push(s,a); Push(s,b); StackTop(s); Pop(s,x); 【 】AaBbC1 D29顺序栈是空栈的条件是 【 】Atop = = 0Btop = = 1Ctop = = -1 Dtop = = m10队列中允许进行插入操作的位置是 【 】A任意端点B队头C队尾 D中间11循环队列Sq是空队列的条件是 【 】ASq read = = Sq frontB(Sq read + 1) % maxsize = = Sq frontCSq read = = 0DSq front= = 012S1 = “abcdecdedcd”，S2 = “cd”，则S2在S1中的位置是 【 】A2B3C4 D513在数组A中，每一个数组元素A i，j 占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是 【 】A80B100C240D27014广义表A(a，A(a，A(a，A() 的深度为 【 】A3B4C5 D15同一个数组中的元素 【 】A长度可以不同B类型不限C类型相同D长度不限16数组与一般线性表的区别主要在 【 】A存储方面B元素类型一致C逻辑结构方面D不能进行插入、删除运算17按照二叉树的定义，3个结点可以构成的二叉树种数为 【 】A3B4C5D618二叉树的叶结点个数比度为2的结点的个数 【 】A无关B多1个C相等D少1个19具有n个结点的完全二叉树的深度为 【 】ABlog2n + 1Clog2nD20已知二叉树的前序遍历顺序和中序遍历顺序，则 【 】A唯一确定一棵二叉树B不能唯一确定一棵二叉树C不能确定二叉树D唯一确定两棵二叉树21树的先根遍历是 【 】A先访问树的根结点B先根遍历根结点的各子树，最后访问根C从左到右依次先根遍历根结点的各子树D先访问树的根结点，再从左到右依次先根遍历根结点的各子树22在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 【 】A1/2倍B1倍C2倍D3倍23有拓扑排序的图，一定是 【 】A有圈图B圈图任意图C无向图D强连通分量24稳定的排序方法是指在排序中，关键字值相等的不同记录间的前后相对位置 【 】A保持不变B保持相反C不定D无关25直接插入排序的方法要求被排序的数据的存储方式为 【 】A顺序B链表C顺序或链表D二叉树26在下列排序方法中，属于不稳定的排序方法的是 【 】A直接插入排序B直接选择排序C冒泡排序D归并排序27索引顺序表的特点是顺序表中的数据 【 】A有序B无序C分块有序D散列28静态查找表的全部运算为 【 】A建表B建表和查找C建表、查找和读表元D查找和读表元29用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为 【 】An Bn/2C(n-1)/2 D(n+1)/230VASM是虚拟存储存取方法，该方法适应的介质是 【 】A磁带或磁盘B光盘C磁带D磁盘参考答案：11A21B31A41A51A61B71C81B91C10C11A12B13C14D15C16D17C18B19A20A21D22B23D24A25A26B27C28D29D30D二、解答题31设广义表C的图形表示如图所示，写出其对应的广义表。xCxzyxy该广义表为C(x,(x,y),(x,y),y,z),(x)32以下面数据作为叶子结点的权值构造一棵哈夫曼树，并计算出其带权路径长度。 17，3，7，8，24，10，16，9，6哈夫曼树如下所示： WPL 24217 10 16 9）3（3 7 8 6）430033已知一个无向图的顶点集为a，b，c，d，e，f，其邻接矩阵如下所示 (1) 画出该图的图形；(2) 分别画出从顶点1出发进行深度优先和广度优先遍历所生成的生成树。答：(1) 该图的图形如下： (2) 深度优先生成树： 广度优先生成树： 34给定关键字集合（45，28，52，20，10，35，40，70，30，75，63，32），(1) 从一棵空的二叉排序树开始，按表中元素的次序构造一棵二叉排序树；(2) 画出从该二叉排序树中删除关键码28和52后的结果。答：(1) 二叉排序树如下： (2) 删除关键码28和52后的二叉排序树如下： 三、程序分析题35对给定的单链表L，下面算法完成删除L中值为x的结点的直接前驱结点，请填空。 void DeleteX(LinkList L, DataType x) /*L是带头结点的单链表*/ListNode * p, * q;q = L; p = L next;while(p & p data != x) q = p; p = ; if( ) Error(“x not in L”); if(q = = L) Error(“x is the first node, it has no prior node”); q data = x; q next = p next; free( ); 答： p next p = = NULL p 36写出下列程序段的输出结果。 void main() Stack S; char x,y; InitStack(S); x = c; y = k; Push(S,x); Push(S,a); Push(S,y); Pop(S,x) Push(S, t); Push(S,x); Pop(S,x); Push(S,s); while(!StackEmpty(S) Pop(S,y); printf(y); printf(x);答：输出结果为： stack37整数集合A的m个元素按由小到大的次序存储在数组a中，整数集合B的n个元素按由小到大的次序存储在数组b中。试分析下面的算法。(1) 该算法完成的功能。(2) 该算法的时间复杂度。 void what(int a, int b, int m, int n, int c,int * ct) int i = 0, j = 0, * ct = 0; while(i m & j n) if(ai = = bj) c(*ct)+ = ai; i +; j+; else if(ai lchild); count(p rchild);(1) 函数count的功能是计算二叉树结点个数，结果放在变量num中。 (2) 调用函数count(root)后，num值为7。四、算法设计题39设顺序表L是一个递增有序表，类型定义如下：#define ListSize 200typedef int DataType;typedef structDataType dataListSize;int length;SeqList;试写一算法将x插入L中使L仍是一个有序表。参考答案如下：void seqinsert(SeqList * L, DataType x) int i, j; for (i = L length 1; i = 0; i- -) if(x = L datai) break; for(j = L length 1; j= i + 1; j- -) L dataj+1 = L dataj; L datai + 1 = x; L length +;40以二叉链表为二叉树的存储结构，写一个算法交换各结点的左右子树。 注：结点结构如下： typedef char DataType; typedef struct nodeDataType data;Struct node * lchild, * rchild;BinTNode