数据结构课程（专科）针对性训练一 中央电大工学院徐孝凯 一、单选愿（每小愿2分，共20分） 1.若一个数据具有集合结构，则元素之间为()： A,线性关系B层次关系C,网状关系D无任何关系 2在一个顺序表的表尾插入一个元素的时阿复杂度为(》。 A.O(m) &0(1) C.O(n#m) D.0(logn) 3在一个长度为n的顺序表中向第1个元素(0运1多n)位置插入一个新元素时，需要 从后白前依次后移《)个元素。 九.ri B.n-i+l C.a-i-1 D.i 4.在一个长度为的线性表中顺序查我值为x的元素时，在等概率情况下，查找成功 时的平均查找长度为()。 A.■ 且.n/2 C.(mt1)/2D.(n-1》/2 点在一个单链表用中，若要在指针所指结点的后面拓入一个由指针p所指向的结点， 则执行()慢作。 A.q->next=p->next:p->next=q:B.p->next=q->mext:q=p: C.q->next=p->next:p=q: D.p->next=q->mext:q->next=p: 6,当利用大小为N的数组顺序存储一个栈时，假定用【0=N表示栈空，则向这个栈插 入一个元素时，首先应执行()操作修政t即指针. A.top++B.top- C.top=0 D.top 7.在一个顺序队列中，队首折针指向队首元素的()位置。 A.后一个B前一个C,当前 D任何 &向二义搜索树中插入一个元素时，其时饲复杂度大政为()， A.O(1aga）R.0) C.0(1) D.0(plogan) 9.一个记录T理论上占有的存储空间的大小等于所有域类型长度之和。实际上占有的 存销空间的大小即记录长度为(》。 A.所有域长度之和 民最大域所占字节长度 C.任意一·个城长度 D.sizeof(r)的值 10,对于长度为9的顺序存储的有序表，若采用二分查载，则平均查找长度为()
1 数据结构课程（专科）针对性训练一 中央电大工学院 徐孝凯 一、单选题（每小题 2 分，共 20 分） 1. 若一个数据具有集合结构，则元素之间为( )。 A. 线性关系 B. 层次关系 C. 网状关系 D. 无任何关系 2. 在一个顺序表的表尾插入一个元素的时间复杂度为( )。 A. O(n) B. O(1) C. O(n*n) D. O(log2n) 3. 在一个长度为 n 的顺序表中向第 i 个元素（0≤i≤n）位置插入一个新元素时，需要 从后向前依次后移（ ）个元素。 A. n-i B. n-i+1 C. n-i-1 D. i 4. 在一个长度为 n 的线性表中顺序查找值为 x 的元素时，在等概率情况下，查找成功 时的平均查找长度为( )。 A. n B. n/2 C. (n+1)/2 D. (n-1)/2 5. 在一个单链表HL中，若要在指针 q所指结点的后面插入一个由指针 p所指向的结点， 则执行( )操作。 A. q->next=p->next; p->next=q; B. p->next=q->next; q=p; C. q->next=p->next; p=q; D. p->next=q->next; q->next=p; 6．当利用大小为 N 的数组顺序存储一个栈时，假定用 top==N 表示栈空，则向这个栈插 入一个元素时，首先应执行( )操作修改 top 指针。 A. top++ B. top-- C. top=0 D. top 7. 在一个顺序队列中，队首指针指向队首元素的( )位置。 A. 后一个 B. 前一个 C. 当前 D.任何 8. 向二叉搜索树中插入一个元素时，其时间复杂度大致为( )。 A. O(log2n ) B. O(n) C. O(1) D. O(nlog2n) 9. 一个记录 r 理论上占有的存储空间的大小等于所有域类型长度之和，实际上占有的 存储空间的大小即记录长度为( )。 A. 所有域长度之和 B. 最大域所占字节长度 C. 任意一个域长度 D. sizeof(r)的值 10. 对于长度为 9 的顺序存储的有序表，若采用二分查找，则平均查找长度为( )
除以9。 A.20 R18 C.25 D.22 二、填空题（每小题2分，共20分） 1.对一个找进行插入或刷除操作的时间复桑度为 2假定单蛙表中的结点结构为(data mext),则在以Ⅲ为表头指针的带表头附知结点 的循环单链表中，链表为空的条件为 3。一个广义表中的元素分为单元素和 元素两类。 4.从一个蛙栈中刷除一个结点时，需要把栈顶结点的指针域的值赋给」 5.在一棵高度为5的理想平衡树中，最少含有个结点。 6.在一个堆的顺序存储中，其堆顾元素的下标为0，若一个元素的下标为3，则它的左 孩子元素的下标为一· 7.在一个具有5个顶点的无向完全图中，但含有 条边。 8.对于一个具有个项点和e条边的有向图。若采用边集数组表示，则存于数组中的 边数为条。 9.在线性表的散列存储中，若用■表示散列表的长度。表示特散列存储的元素的个 数，则装填因子等于 10.。在一棵4阶B树上，每个事树根结点的子树数目最少为 个 三、运算题（每小题6分，共24分） 1.假定一个大服堆为36,38,42,3025,40,35,20)，则向它插入45元素后得到的大服 堆为 2.己知一个图的顶点集V和边集G分别为 V-0.1,2.34,5 =0,10.0,2),0,3),(1,5,2,3》,(240,(a5),(4.51 假定该图深用忽接矩阵表示，则分别写出从项点2出发进行深度优先搜索海历和广度优 先搜素寿历得到的顾点序列： 深度优先搜索序列： 广度优先授索序列山 3.假定一个顺序表为(15,283站，45.8,72.83动，则利用二分查找方法查找元素36时， 其查找长度（即所需比较元煮的个数）为 4.假定一组记求的排序码为(40803第，64.T5,6646,79.56,38.84.25),对其进行日并 2
2 除以 9。 A. 20 B. 18 C. 25 D. 22 二、填空题（每小题 2 分，共 20 分） 1. 对一个栈进行插入或删除操作的时间复杂度为___________。 2. 假定单链表中的结点结构为(data next)，则在以 HL 为表头指针的带表头附加结点 的循环单链表中，链表为空的条件为____________。 3．一个广义表中的元素分为单元素和________元素两类。 4．从一个链栈中删除一个结点时，需要把栈顶结点的指针域的值赋给____________。 5．在一棵高度为 5 的理想平衡树中，最少含有________个结点。 6．在一个堆的顺序存储中，其堆顶元素的下标为 0，若一个元素的下标为 3，则它的左 孩子元素的下标为________。 7．在一个具有 5 个顶点的无向完全图中，包含有________条边。 8．对于一个具有 n 个顶点和 e 条边的有向图，若采用边集数组表示，则存于数组中的 边数为________条。 9．在线性表的散列存储中，若用 m 表示散列表的长度，n 表示待散列存储的元素的个 数，则装填因子等于__________。 10．在一棵 4 阶 B_树上，每个非树根结点的子树数目最少为________个。 三、运算题（每小题 6 分，共 24 分） 1. 假定一个大根堆为(56,38,42,30,25,40,35,20)，则向它插入 45 元素后得到的大根 堆为__________________________________。 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)} 假定该图采用邻接矩阵表示，则分别写出从顶点 2 出发进行深度优先搜索遍历和广度优 先搜索遍历得到的顶点序列。 深度优先搜索序列： 广度优先搜索序列： 3．假定一个顺序表为(15,28,36,45,48,72,83)，则利用二分查找方法查找元素 36 时， 其查找长度（即所需比较元素的个数）为___________。 4．假定一组记录的排序码为(40,80,36,64,75,66,46,79,56,38,84,25)，对其进行归并
排序的过程中，第二植归并后的结果为： 四、阅读算法，回答问题（每小题8分，共16分） L.void A超(List&LD InsertRear(L.30); InsertFront(L 58): Delete(L,12): InsertRear(L,DeleteFront (L)); 假定调用该算法封线性表L为(35,19,12,15)，则调用返回后线性表L变为： 2写出下面递归算法的功能，假定围.为一个单链表的表头指针。 vold C2(LNode*HL) if (HL!-NULL) C2(HL->next) cout data<<''; 算法功能： 五、算法填空，在百有横战的地方填写合适的内容（年每小题6分，共12分）： 1.下面是从一雏量组A]中二分查找关健字为区的元素的丰递归算法，若查找成功则 返回对应元素的下标，否则返回-1： int Binsch(ElemType A[,int m.KeyType K) int low-0.high"n-1; while(low<=high) int mid;
3 排序的过程中，第二趟归并后的结果为： _________________________________________________。 四、阅读算法，回答问题（每小题 8 分，共 16 分） 1. void AB(List& L) { InsertRear(L,30); InsertFront(L,58); Delete(L,12); InsertRear(L,DeleteFront(L)); } 假定调用该算法时线性表 L 为(35,19,12,15)，则调用返回后线性表 L 变为： ____________________________。 2. 写出下面递归算法的功能，假定 HL 为一个单链表的表头指针。 void C2(LNode* HL) { if(HL!=NULL) { C2(HL->next); coutdata<<' '; } } 算法功能： 五、算法填空，在画有横线的地方填写合适的内容(每小题 6 分，共 12 分)。 1. 下面是从一维数组 A[n]中二分查找关键字为 K 的元素的非递归算法，若查找成功则 返回对应元素的下标，否则返回-1。 int Binsch(ElemType A[], int n, KeyType K) { int low=0, high=n-1; while(low<=high) { int mid;
fd年(1ow+high)/2: if( )return mid: else if(KCA[mid].key) else return -1: 2下面重递自算法的功能为从ST所指向的二义搜索树中查找出值为1tm的元素，若 查找成功返目真，否则返目假。 bool Find(BTreeNode*BST.ElenType item) while(BST!=NLL) if(item--BST->data) else if(itendata) else 1 return false 六、输马算法（⑧分） 根据下面函数声明编写算法，向类型为List的线性表L中第1个元煮位置(0写i写 Lsxe)插入一个元素的算法，假定不需要对1的值进行有效性检查，同时不需要检查存储 空间是否用完。 void Insert (List&L.int i.EleaType x): 4
4 mid=(low+high)/2; if(_______________) return mid; else if(Kdata) ______________; else if(itemdata) ______________; else ______________; } return false ; } 六、编写算法(8 分) 根据下面函数声明编写算法，向类型为 List 的线性表 L 中第 i 个元素位置（0≤i≤ L.size）插入一个元素的算法，假定不需要对 i 的值进行有效性检查，同时不需要检查存储 空间是否用完。 void Insert(List& L, int i, ElemType x);
答案供参考 一、单选题（每小题2分，共20分） 评分标准，选对者得2分，否则不得分。 1.D2.B3.A4.C&D 6.B 7.B 8.A 9.D10.C 二、填空厘（每小题2分，共20分） 1.0(1) 2.HL->next==HL 3表（或子表） 4栈项指针 &.16 67 7.10 8.e 9.n/m 10.2 三、运算愿（每小愿6分，共24分） 1.(56.45,42.38,25.40,35,20,30) 2深度优先搜素序列：2,0.1,5,3.4 /3分 广度优先搜素序列：2,03,4,1.5 //3分 33 4.【36408480][46667579[25385684] 四、阅读算法，回答间题（每小题8分，共16分） 1.(35.19,15.30,580 2按逆序〔即原歧接的相反次序)输出以L为表头指针的单皓表中的每个结点的值。 五、算法填空，在蕴有横战的地方填写合适的内容（每小题6分，共12分） 1.k=-A[mid].key high"nid-1 low-mid+l /每个空2分 2 return true BST-BST->left BST=BST->right /每个空2分 六、编写算法⑧分) 评分标准：根据编程完整程度的情给分。 void Insert (List&L,int i,EleaType x) for(int j=L size-1:j>=i:j-) L list[j+l]-L.list[j]: 114分 Llist(i]=x: /%分
5 答案供参考 一、单选题（每小题 2 分，共 20 分） 评分标准：选对者得 2 分，否则不得分。 1. D 2. B 3. A 4. C 5. D 6. B 7. B 8. A 9. D 10. C 二、填空题（每小题 2 分，共 20 分） 1. O(1) 2. HL->next==HL 3. 表（或子表） 4. 栈顶指针 5. 16 6. 7 7. 10 8. e 9. n/m 10. 2 三、运算题（每小题 6 分，共 24 分） 1. (56,45,42,38,25,40,35,20,30) 2. 深度优先搜索序列： 2,0,1,5,3,4 //3 分 广度优先搜索序列： 2,0,3,4,1,5 //3 分 3. 3 4. [36 40 64 80][46 66 75 79][25 38 56 84] 四、阅读算法，回答问题（每小题 8 分，共 16 分） 1. (35,19,15,30,58) 2. 按逆序（即原链接的相反次序）输出以 HL 为表头指针的单链表中的每个结点的值。 五、算法填空，在画有横线的地方填写合适的内容(每小题 6 分，共 12 分) 1. k==A[mid].key high=mid-1 low=mid+1 //每个空 2 分 2. return true BST=BST->left BST=BST->right //每个空 2 分 六、编写算法(8 分) 评分标准：根据编程完整程度酌情给分。 void Insert(List& L, int i, ElemType x) { for(int j=L.size-1; j>=i; j--) L.list[j+1]=L.list[j]; //4 分 L.list[i]=x; //6 分
L.sizett; 1/7分 1/8分 6
6 L.size++; //7 分 } //8 分