数据结构课程（专料）针对性训陈二 中央电大工学院徐孝凯 一、单选愿（每小愿2分，共20分） 1,在一个长度为的线性表中顺序查找值为x的元素时，在等概率情况下查找成功时 的平均查找长度为()。 A■ B.n/2 C.(n+1)/2 D.-1)/2 2.栈的插入和刷除操作在()进行. A栈顶 R慢底 C.任意位置 D.指定位置 3在一个顺序队列中，队尾折针指向队尾元素的()位置： A.前一个B后一个 C,当前 D,后两个 4.在一棵树中，每个结点最多有( )个前更结点。 A.0 .1C.2 D.任意多个 反与图的邻接矩库表示方法相比，氢接表更适合于存错()。 A.无向图B。连通图C.稀陵图D.稠密图 6从堆中剩除一个元需的时间复杂度为()， A.0(1) B.O(logn) C.O(n) D.O(plog-) 7.对于以表头指针为ist的单链表，该表为空的判定条件是()。 A.first NULL: B.first->next=NULL: C.first->mext==first: D.first!=NULL: 8如果一个递归函数过程中的所有递归语句那是可执行的最后一条语句，调将这种递 归过程为《)，它很容易被改写为非递归过程。 A.单向递自且回满递归C,间接递自D.来尾通归 9根据个元素建立一棵二叉授素树时，其时间复桑度大致为()。 A.0} B01agn）C,0(n) D.0(nla陆 10,利用个植作为叶结点的权而生成的哈夫受树中共包含有()个结点。 A日 B+1 C,2知 02知-1 二、填空题（每小题2分，共20分） 1.数据的 技分为集合结构、线性结构，树结构和图结构四种
数据结构课程（专科）针对性训练二 中央电大工学院 徐孝凯 一、单选题（每小题 2 分，共 20 分） 1. 在一个长度为 n 的线性表中顺序查找值为 x 的元素时，在等概率情况下查找成功时 的平均查找长度为( )。 A. n B. n/2 C. (n+1)/2 D. (n-1)/2 2．栈的插入和删除操作在( )进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 3. 在一个顺序队列中，队尾指针指向队尾元素的( )位置。 A. 前一个 B. 后一个 C. 当前 D. 后两个 4. 在一棵树中，每个结点最多有( )个前驱结点。 A. 0 B. 1 C. 2 D. 任意多个 5. 与图的邻接矩阵表示方法相比，邻接表更适合于存储( )。 A．无向图 B．连通图 C．稀疏图 D．稠密图 6. 从堆中删除一个元素的时间复杂度为( )。 A. O(1) B. O(log2n) C. O(n) D. O(nlog2n) 7. 对于以表头指针为 first 的单链表，该表为空的判定条件是（ ）。 A. first == NULL; B. first->next==NULL; C. first->next==first; D. first!=NULL; 8. 如果一个递归函数过程中的所有递归语句都是可执行的最后一条语句，则称这种递 归过程为（ ），它很容易被改写为非递归过程。 A. 单向递归 B. 回溯递归 C. 间接递归 D. 末尾递归 9. 根据 n 个元素建立一棵二叉搜索树时，其时间复杂度大致为( )。 A. O(n) B. O(log2n ) C. O(n2 ) D. O(nlog2n) 10. 利用 n 个值作为叶结点的权而生成的哈夫曼树中共包含有( )个结点。 A. n B. n+1 C. 2*n D. 2*n-1 二、填空题（每小题 2 分，共 20 分） 1. 数据的____________被分为集合结构、线性结构、树结构和图结构四种
2对于一个长度为m的顺序存储的线性表，在表头插入元素的时间复桑度为 3在一个稀流矩库中，每个丰零元素所对应的三元姐色括该元素的行号、和 值三项。 4,一樱高度为5的满二义树中含有个结点。 反在一个小根蜂中，堆项结点的值是所有结点中的一· 6在一个具有个顶点的无向图中，要连通所有项点则至少需要 条边。 7.假定一个图具有个顶点和e条边，若采用邻接矩阵表示时，其空间复杂度为 8.以二分直找方法查找一个顺序存储的线性表时，此线性表必须是一个表。 9。在索到表中，若一个素引项对应主表中的 条记录，则称北素引为两密索引。 10.快速排序在平均情况下的空间复条度为 三、运算愿（每小题6分，共24分） 1.假定一棵二叉树广文表表示为AB(,D),C(E(G们，)，分别写出对它进行先序、中序 和按层寿历的结果。 先序 中序： 按层 2.已知一个有向图的顾点集V和边集G分别为： V=0,1,2.3,4,5别： E-0,1).0,2>.1,5>.2,3>,2.4>,30,35》》: 假定该图采用氢接表表示，井假定每个顶点邻接表中的边结点是按盟顶点序号从大到小 的次序链接的，试写出从顶点0出发分别进行深度优先搜索遍历和广度优先搜索遍历得到的 顶点序列。 深度优先搜索序列： 广度优先慢索序列： 3,假定对线性表(38.25,74,52,8,65,3)进行散列存储，若采用H(K)=或%9作为散列 函数，并采用链接法处理冲突，则查找长度分别为12,3的元素个数对应为一、一 和一· 4.假定一组记录的排序码为(46,79.56,38,40,80,25,73)，则对其进行快速排序的第一 次划分后的结果为
2. 对于一个长度为 n 的顺序存储的线性表，在表头插入元素的时间复杂度为________。 3. 在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的行号、________和 值三项。 4．一棵高度为 5 的满二叉树中含有________个结点。 5. 在一个小根堆中，堆顶结点的值是所有结点中的________。 6. 在一个具有 n 个顶点的无向图中，要连通所有顶点则至少需要________条边。 7. 假定一个图具有 n 个顶点和 e 条边，若采用邻接矩阵表示时，其空间复杂度为 ________。 8．以二分查找方法查找一个顺序存储的线性表时，此线性表必须是一个________表。 9．在索引表中，若一个索引项对应主表中的________条记录，则称此索引为稠密索引。 10．快速排序在平均情况下的空间复杂度为__________。 三、运算题（每小题 6 分，共 24 分） 1. 假定一棵二叉树广义表表示为 A(B(,D),C(E(G),F))，分别写出对它进行先序、中序 和按层遍历的结果。 先序： 中序： 按层： 2．已知一个有向图的顶点集 V 和边集 G 分别为： V={0,1,2,3,4,5}; E={,,,,,,}; 假定该图采用邻接表表示，并假定每个顶点邻接表中的边结点是按照顶点序号从大到小 的次序链接的，试写出从顶点 0 出发分别进行深度优先搜索遍历和广度优先搜索遍历得到的 顶点序列。 深度优先搜索序列： 广度优先搜索序列： 3．假定对线性表(38,25,74,52,48,65,36)进行散列存储，若采用 H(K)=K % 9 作为散列 函数，并采用链接法处理冲突，则查找长度分别为 1、2、3 的元素个数对应为_______、_______ 和__________。 4. 假定一组记录的排序码为(46,79,56,38,40,80,25,73)，则对其进行快速排序的第一 次划分后的结果为______________________________________
四、阅读算法，回答问愿（每小题8分，共16分） 1.void AC(List&L) InitList (1) InsertRear (L 25); InsertFront (L 50) inta[4J=(8.12.15,36: for(int i-0:i(4:i++)InsertFront (L,a[i]): 该算法被调用执行后，得到的线性表L为： 2.void AG(Queuek Q) InitQueue (Q): inta[5)-6.12,5,15,8: for (int i=0:ileft,x)+BTreeCount (BT->right,x)+1: else return BTreeCount BI->left.x)+
四、阅读算法，回答问题（每小题 8 分，共 16 分） 1. void AC(List& L) { InitList(L); InsertRear(L,25); InsertFront(L,50); int a[4]={8,12,15,36}; for(int i=0;ileft, x)+BTreeCount(BT->right, x)+1; else return BTreeCount( BT->left, x)+__________________________; }
2下面函数的功能是从二叉树T中查找值为X的结点，若查找成功则运回结点地址， 否则返回空， BinTreeNode BTF(BinTreeNode BI,EleaType x) if (BT==NULL) else{ if(BT->data==x) else BinTreeNode*t: if(t=BTF(BT->left.x))return t: 1f(t= _return t: return NULL: 六、编写算法（⑧分） 根据下面函数原型，编写一个遥归算法，统计并返目以T为树根指针的二叉树中所有 叶子结点的个数， int Count (BTreeNode*BT);
2.下面函数的功能是从二叉树 BT 中查找值为 X 的结点，若查找成功则返回结点地址， 否则返回空。 BinTreeNode* BTF(BinTreeNode* BT, ElemType x) { if(BT==NULL) _______________; else { if( BT->data==x) ______________; else { BinTreeNode* t; if(t=BTF(BT->left, x)) return t; if(t=______________________) return t; return NULL; } } } 六、编写算法(8 分) 根据下面函数原型， 编写一个递归算法，统计并返回以 BT 为树根指针的二叉树中所有 叶子结点的个数。 int Count(BTreeNode* BT);
答案供参者 一、单进题（每小题2分，共20分） 评分标准：选对者得2分，否则不得分。 1.C2.A3.C4.B&.C 6B7.A8.D9.D10.D 二、填空框（每小题2分，共20分） 1.逐铜结构 2.0m 及列号 4.31 及最小值 6.r-1 7.0(m7 8.有序 9.- 10.0(1ogn） 三、运算愿（每小题6分，共24分） I.先序：A,BD,CEG,F /2分 中序：BDA,G,EC,F: 12分 按层：A,BC,D,EF,G 12分 之深度优先搜素序列：0,24,3,5,1 1/3分 广度优先搜素序列：0,21,4,3,5 /13分 34.2.1 /每个数据2分 4.【382540j46[56807973 四、阅读算法，国客问愿（每小愿8分，共16分） 评分标准：根据情况情给分。 1.(3615,12.8,50,25) 2125158620 五、算法填空，在西有横线的地方填写合适的内容（每小愿6分，共12分）， I.retm0BT->data>x BTreeCount(BT->right,x)/6分，每空2分 2 return NULL return BT BTF(BT->right,x) /8分。每空2分 六、输写算法(8分) 评分标谁：请根据编程的完整情况的情给分。 int Count (BTreeNode*BT) /统计出二叉树中所有叶子结点数
答案供参考 一、单选题（每小题 2 分，共 20 分） 评分标准：选对者得 2 分，否则不得分。 1. C 2. A 3. C 4. B 5. C 6. B 7. A 8. D 9. D 10. D 二、填空题（每小题 2 分，共 20 分） 1. 逻辑结构 2. O(n) 3. 列号 4. 31 5. 最小值 6. n-1 7. O(n2 ) 8. 有序 9. 一 10. O(log2n) 三、运算题（每小题 6 分，共 24 分） 1. 先序：A,B,D,C,E,G,F; //2 分 中序：B,D,A,G,E,C,F; //2 分 按层：A,B,C,D,E,F,G //2 分 2. 深度优先搜索序列：0,2,4,3,5,1 //3 分 广度优先搜索序列：0,2,1,4,3,5 //3 分 3. 4,2,1 //每个数据 2 分 4. [38 25 40] 46 [56 80 79 73 四、阅读算法，回答问题（每小题 8 分，共 16 分） 评分标准：根据情况酌情给分。 1. (36,15,12,8,50,25) 2. 12 5 15 8 6 20 五、算法填空，在画有横线的地方填写合适的内容(每小题 6 分，共 12 分)。 1. return 0 BT->data>x BTreeCount( BT->right, x) //6 分，每空 2 分 2. return NULL return BT BTF(BT->right, x) //6 分，每空 2 分 六、编写算法(8 分) 评分标准：请根据编程的完整情况酌情给分。 int Count(BTreeNode* BT) //统计出二叉树中所有叶子结点数
if(BT--NULL)return 0; 1/2分 else if (BT->left==NULL BT->right==NULL)return 1://4 else return Count(BT->left)+Count (BT->right): /n分 /8分
{ if(BT==NULL) return 0; //2 分 else if(BT->left==NULL && BT->right==NULL) return 1; //4 分 else return Count(BT->left)+Count(BT->right); //7 分 } //8 分