数据结构课程（专料）针对性训陈四 中央电大工学院徐李凯 一、单选愿（每小愿2分，共20分） 1。在一个长度为的顺序存锦的线性表中，插入一个元素的时间复杂度为()。 A.0(n) B0(n/2) C.0(1) D.0m) 2在一个长度为n的顺序存铺的线性表中，副除第1个元素(0≤1≤一1)时，需要从 前向后依次前移(》个元素。 A一i B.n-i+l C.mi-1 D.i 及设一个广义表中结点的个数为，则求广义表深度算法的时间复杂度为()， A.0(1) B.0(n) D.0(logn) 4假定一个顺序队列的队首和风尾霸针分别为「和，则判断队空的条件为()。 A.felmmr B.r+lemf C.f-0 D.fer 点在由表头指针↑所指向的循环单链表中，只含有一个结点的判断条件为()。 A.f->next==NULL: B.f==NULL: C.f->next=f; Df->ext！=f: 6在一保二叉树的二叉蛙表中，空行针拔数等于结点数加()， A.2 B.I C.0 D.-1 工.从二叉搜索树中查找一个元素时，其时间复杂度大政为( . A.0(n) B0(1 C.0(1agn.0(m &在一棵5阶B树中，树根结点最多允许有()个关键字。 A.1B2 C.3n.4 9.二分查找过程所对应的判定树，既是一保理塑平衡树，又是一保 A一般二叉树B,二叉搜索树C,满二叉树 以.完全二叉树 10。在对个元素进行直找选择排序的过程中，需要进行()墙这择和交换。 A.-1 B.n C.n+l D.n/2 二、填空愿（每小题2分，共20分） 1.数据的 结构按分为顺序、链接、索引和散列四种结构。 2对于一个长度为的单链接存储的线性表，在表头插入结点的时间复染度为 1
1 数据结构课程（专科）针对性训练四 中央电大工学院 徐孝凯 一、单选题（每小题 2 分，共 20 分） 1. 在一个长度为 n 的顺序存储的线性表中，插入一个元素的时间复杂度为( )。 A. O(n) B. O(n/2) C. O(1) D. O(n2 ) 2. 在一个长度为 n 的顺序存储的线性表中，删除第 i 个元素（0≤i≤n-1）时，需要从 前向后依次前移( )个元素。 A. n-i B. n-i+1 C. n-i-1 D. i 3. 设一个广义表中结点的个数为 n，则求广义表深度算法的时间复杂度为( )。 A. O(1) B. O(n) C. O(n2 ) D. O(log2n) 4. 假定一个顺序队列的队首和队尾指针分别为 f 和 r，则判断队空的条件为( )。 A. f+1==r B. r+1==f C. f==0 D. f==r 5. 在由表头指针 f 所指向的循环单链表中，只含有一个结点的判断条件为（ ）。 A. f->next==NULL; B. f==NULL; C. f->next==f; D. f->next!=f; 6. 在一棵二叉树的二叉链表中，空指针域数等于结点数加( )。 A. 2 B. 1 C. 0 D. –1 7. 从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2 ) 8. 在一棵 5 阶 B 树中, 树根结点最多允许有（ ）个关键字。 A. 1 B. 2 C. 3 D. 4 9．二分查找过程所对应的判定树，既是一棵理想平衡树，又是一棵____________。 A. 一般二叉树 B. 二叉搜索树 C. 满二叉树 D. 完全二叉树 10．在对 n 个元素进行直接选择排序的过程中，需要进行（ ）趟选择和交换。 A. n-1 B. n C. n+1 D. n/2 二、填空题（每小题 2 分，共 20 分） 1. 数据的__________结构被分为顺序、链接、索引和散列四种结构。 2. 对于一个长度为 n 的单链接存储的线性表，在表头插入结点的时间复杂度为 ________
3,在一棵深度为3的满四叉树中，其结点总数为个。 4,从一棵二义搜索树中查找一个元素时，若给定值小于树根结点的值，则继续向树根 结点的 子树查找。 5,当从一个堆中剩除一个元素时，需要把堆尾元素填补到位置，然后再对它 进行裤运算， 6对于一个具有个项点和e条边的连通图。其任一生成树中的边数为 条。 7.二分查找过程所对应的判定树既是一棵树，又是一棵二叉搜索树。 &若对长度=000的线性表进行二级索升存储，每级索H表中的素引项是下一级10 个记豪的素羽。则二级素羽表的长度为。 9。在一保■阶的B树中，每个结点的子树数目最多为一个。 10.在自并排序中，进行每趟归并的时间复杂度为 三、运算愿（每小题6分，共24分） 1.假定一棵二叉树广文表表示为a6(c,d),e(f(》),分别写出对它进行先序、中序 和后序寿历的结果。 先序 中序： 后序 2.已知一个图的顶点集V和边集G分别为： V=01,2,3,4,5别 E-{0,1).0,2),0,3),(1,5,2.3》,(20,(3.5,(4,5] 假定该图采用氢接矩阵表示，则分别写出从顶点0出发进行深度优先搜索希历和广度优 先搜需寿历得到的顶点序列： 深度优先授素序列： 广度优先搜索序列： 怎已知一个带权图的厦点集V和边集G分别为： V=0,1,2.34,5d E={0,1)12(0,205,(0302,(1,5)10,(23)6.2,40153,5)91: 写出按盟克鲁斯卡尔算法依次得到该图的最小生成树中的各条边，以及最小生成树的 权。 各条边： 2
2 3．在一棵深度为 3 的满四叉树中，其结点总数为________个。 4．从一棵二叉搜索树中查找一个元素时，若给定值小于树根结点的值，则继续向树根 结点的________子树查找。 5．当从一个堆中删除一个元素时，需要把堆尾元素填补到________位置，然后再对它 进行筛运算。 6. 对于一个具有 n 个顶点和 e 条边的连通图，其任一生成树中的边数为________条。 7．二分查找过程所对应的判定树既是一棵____________树，又是一棵二叉搜索树。 8. 若对长度 n=1000 的线性表进行二级索引存储，每级索引表中的索引项是下一级 10 个记录的索引，则二级索引表的长度为________。 9．在一棵 m 阶的 B_树中，每个结点的子树数目最多为________个。 10. 在归并排序中，进行每趟归并的时间复杂度为_________。 三、运算题（每小题 6 分，共 24 分） 1. 假定一棵二叉树广义表表示为 a(b(c,d),e(f(,g)))，分别写出对它进行先序、中序 和后序遍历的结果。 先序： 中序： 后序： 2．已知一个图的顶点集 V 和边集 G 分别为： V={0,1,2,3,4,5} E={(0,1),(0,2),(0,3),(1,5),(2,3),(2,4),(3,5),(4,5)} 假定该图采用邻接矩阵表示，则分别写出从顶点 0 出发进行深度优先搜索遍历和广度优 先搜索遍历得到的顶点序列。 深度优先搜索序列： 广度优先搜索序列： 3. 已知一个带权图的顶点集 V 和边集 G 分别为： V={0,1,2,3,4,5}; E={(0,1)12,(0,2)5,(0,3)2,(1,5)10,(2,3)6,(2,4)15,(3,5)9}; 写出按照克鲁斯卡尔算法依次得到该图的最小生成树中的各条边，以及最小生成树的 权。 各条边：________, ________, ________, ________, ________
最小生成树的权： 4.假定一组记录的排序码为《46,79.56,38,40,80,25)，在对其进行快速排序的过程中， 进行第一次划分后得到的排序码序列为。 排序列序列 四、阅读算法，回答间题（每小题8分，共16分） I.void AD (LNodes4厘) Insert (HL,30): /在有序单链表上进行有序插入 Insert (HL,50): /在有序单随表上进行有序精入 Delete(HL,28) Delete(HL,53) 置定调用该算法时以L为表头指针的有序单链表中的内容为28,3642,53,6，则给 出调用返回后该有序单链表中的内容。 有序单链表中的内容： 2.void Al (adjmatrix GA,int i,int n) comt<《i('" visited[i]=true: for(int j=0:j(n:j++)( bool b=GA[i][j]!=0 GA[i][j]!=MaxValue Ivisited[j]: if(b)AI (GA,j.n) 该算法的功能为： 五、算法填空，在酒有横战的地方填写合适的内容（每小题6分，共12分）： 1,向以ST为树根指针的二叉授素树上插入值为tem的结点的丰递归算法。 void Insert (BTreeNode*&BST,const ElemTypek item) BTreeNode*t=BST,*parent=NULL: 3
3 最小生成树的权： 4. 假定一组记录的排序码为(46,79,56,38,40,80,25)，在对其进行快速排序的过程中， 进行第一次划分后得到的排序码序列为。 排序码序列： 四、阅读算法，回答问题（每小题 8 分，共 16 分） 1. void AD(LNode*& HL) { Insert(HL,30); //在有序单链表上进行有序插入 Insert(HL,50); //在有序单链表上进行有序插入 Delete(HL,28); Delete(HL,53); } 假定调用该算法时以 HL 为表头指针的有序单链表中的内容为(28,36,42,53,66)，则给 出调用返回后该有序单链表中的内容。 有序单链表中的内容： 2. void AI(adjmatrix GA, int i, int n) { cout<<i<<' '; visited[i]=true; for(int j=0; j<n; j++){ bool b=GA[i][j]!=0 && GA[i][j]!=MaxValue && !visited[j]; if(b) AI(GA,j,n); } } 该算法的功能为： 五、算法填空，在画有横线的地方填写合适的内容(每小题 6 分，共 12 分)。 1. 向以 BST 为树根指针的二叉搜索树上插入值为 item 的结点的非递归算法。 void Insert(BTreeNode*& BST, const ElemType& item) { BTreeNode* t=BST, *parent=NULL;
hile(tI-L》 parent=t: if(itemdata)t"t->left: else BTreeNode*p"nex BTreeNode: p->data=item:p->left=p->right=NULL: if(parent==NULL)BST=p: else if(item(parent->data)parent->left-p: else 2从类型为Lst的线性表L中到除与x值相等的所有元素。 void Delete2(List&L.ElesType x) int i=0: while(i(L.size） ifL.1ist[i]-)【 for(int j=i+1:jLsixe:j++) Llist[j-1]- Lsz0-一： else 六、编可算法（⑧分） 编写从类型为Lst的线性表L中到除其值等于给定值x的第一个元素的算法，要求若 剩除成功返目tue,否则返回false, bool Delete(List&L,ElemType x):
4 while(t!=NULL) { parent=t; if(itemdata) t=t->left; else ________________; } BTreeNode* p=new BTreeNode; p->data=item; p->left=p->right=NULL; if(parent==NULL) BST=p; else if(itemdata) parent->left=p; else ____________________; } 2. 从类型为 List 的线性表 L 中删除与 x 值相等的所有元素。 void Delete2(List& L, ElemType x) { int i=0; while(i<L.size) { if(L.list[i]==x) { for(int j=i+1; j<L.size; j++) L.list[j-1]=____________; L.size--; } else ____________; } } 六、编写算法(8 分) 编写从类型为 List 的线性表 L 中删除其值等于给定值 x 的第一个元素的算法，要求若 删除成功返回 true，否则返回 false。 bool Delete(List& L, ElemType x);
(答案供参考) 一、单进题（每小题2分，共20分） 评分标准：选对者得2分，否则不得分。 1.A2.C3.B4.D6.C 6B7.C8.D9.B10A 二、填空框（每小题2分，共20分） 1.存储《物理) 2.0(10 321 4.左 及堆项 6.r1 7。理想平衡 8.10 9.国 10.0(n) 三、运算愿（每小题6分，共24分） 1.先序：a,b,C,de,E,g 1/2分 中序：c,b,d,a,f,R,e 12分 后序，C,4b,g.f,,a I/2分 2深度优先搜素序列：0,1.5,3,4,2 13分 广度优先擅素序列：0,1.2,3,54 13分 3各条边：(03)2.(0,2)5.(3,5)9，(1,5)10，(2.4015 /4分 最小生成树的权：4和 /2分 4.(38.25,40.46,56.80,79) /6分，的情给分 四、阅读算法，回答间题（每小题8分，共16分） 1.(30.36,42.50,66) /全对给6分，否则的情给分 2从初始点？，出发深度优先授素奢历由邻接矩库A所表示的图。 评分标准：请根据叙述的完整情况的情给分。 五、算法填空，在西有横战的地方填写合适的内容（每小题6分，共12分）。 1.t=t->right parent->right=p /每空对给3分 2L.1ist[j】i+ /每空对给3分 六、编写算法⑧分) 评分标准：根据偏程的完整情况酌情给分。 bool Delete(List&L.ElenType x)
5 （答案供参考） 一、单选题（每小题 2 分，共 20 分） 评分标准：选对者得 2 分，否则不得分。 1. A 2. C 3. B 4. D 5. C 6. B 7. C 8. D 9. B 10. A 二、填空题（每小题 2 分，共 20 分） 1. 存储（物理） 2. O(1) 3. 21 4.左 5. 堆顶 6. n-1 7. 理想平衡 8. 10 9. m 10. O(n) 三、运算题（每小题 6 分，共 24 分） 1. 先序： a,b,c,d,e,f,g //2 分 中序： c,b,d,a,f,g,e //2 分 后序： c,d,b,g,f,e,a //2 分 2. 深度优先搜索序列： 0,1,5,3,4,2 //3 分 广度优先搜索序列： 0,1,2,3,5,4 //3 分 3. 各条边：(0,3)2, (0,2)5, (3,5)9, (1,5)10, (2,4)15 //4 分 最小生成树的权：41 //2 分 4. (38,25,40,46,56,80,79) //6 分，酌情给分 四、阅读算法，回答问题（每小题 8 分，共 16 分） 1. (30,36,42,50,66) //全对给 6 分，否则酌情给分 2. 从初始点 vi 出发深度优先搜索遍历由邻接矩阵 GA 所表示的图。 评分标准：请根据叙述的完整情况酌情给分。 五、算法填空，在画有横线的地方填写合适的内容(每小题 6 分，共 12 分)。 1. t=t->right parent->right=p //每空对给 3 分 2. L.list[j] i++ //每空对给 3 分 六、编写算法(8 分) 评分标准：根据编程的完整情况酌情给分。 bool Delete(List& L, ElemType x) {
for(int i=0:i<Lsize:i+)if(Llist[i]==x)break: 113分 if(i=size)return false 1/4分 for(int j=i+l:jL.size:j)Llist[j-1]=Llist[j]; 6分 L.size- n分 return true; 1/8分 1
6 for(int i=0; i<L.size; i++) if(L.list[i]==x)break; //3 分 if(i==L.size) return false; //4 分 for(int j=i+1; j<L.size; j++) L.list[j-1]=L.list[j]; //6 分 L.size--; //7 分 return true; //8 分 }