数据结构课程（专料）针对性训陈三 中央电大工学院徐举凯 一、单选愿（每小愿2分，共20分） 1,在函数调用中，当需要修改一个实际参数的值时，则对应的形式参数应被说明为 ()参数. A.值R。引用C,指针 D.常量引用 2向一个长度为的顺序表中插入一个新元素的平均时间复染度为()： A.O(n) B01》 C.o(n')D.O(logn) 及根据一个长度为m的单链表的表头指针皿，向其表尾精入一个新结点的时间复杂度 为(）。 A.0 &0n/2) C.0(I D.0) 4.在一个单链表Ⅲ中，若要向表头插入一个由指针P所指向的结点，则执行()。 A.HL=p:p->next=L: B,r>next=:l印 C.p->next=L:pL; D.p->next=->next:HL->next=p: 5.当利用大小为N的数组顺序存储一个钱时，假定用top-N表示找空，用t0p0表 示栈满。则向这个栈插入一个元素时，首先应执行()操作修政t即指针。 A.top++B.top--C.top-0 D.top=N 6在具有n个项点的强连通图中至少含有(）条有向边。 A.s-1 B.n C,n(n-l)/2 D.n(n-1) 7.从一棵二义被索树中查找一个元素时，其时间复杂度大致为()。 B.0I)A.0 C.o(logn)D.o(n) 8由权值分别为3,8,62的四叶子结点生成一棵哈夫曼树，它的蒂权路径长度为 () A.24 B.38C190.35 9.若根据数据集合23,4,36,8,52.73,64,58建立胜列表，采用h)=13计算散列 地址，并果用鲑接法处理冲突，则元素64的散列地址为()。 A.4 B.8 C.12n.13 10,在一保5阶B树中，每个结点最多允许有()个关健字。 A.2B.3C.4n.5 1
1 数据结构课程（专科）针对性训练三 中央电大工学院 徐孝凯 一、单选题（每小题 2 分，共 20 分） 1. 在函数调用中，当需要修改一个实际参数的值时，则对应的形式参数应被说明为 ( )参数。 A. 值 B. 引用 C. 指针 D. 常量引用 2. 向一个长度为 n 的顺序表中插入一个新元素的平均时间复杂度为（ ）。 A. O(n) B. O(1) C. O(n2 ) D. O(log2n) 3. 根据一个长度为 n 的单链表的表头指针 HL，向其表尾插入一个新结点的时间复杂度 为( )。 A. O(n) B. O(n/2) C. O(1) D. O(n2 ) 4. 在一个单链表 HL 中，若要向表头插入一个由指针 p 所指向的结点，则执行( )。 A. HL=p; p->next=HL; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. p->next=HL->next; HL->next=p; 5．当利用大小为 N 的数组顺序存储一个栈时，假定用 top==N 表示栈空，用 top==0 表 示栈满，则向这个栈插入一个元素时，首先应执行( )操作修改 top 指针。 A. top++ B. top-- C. top=0 D. top=N 6. 在具有 n 个顶点的强连通图中至少含有( ) 条有向边。 A．n-1 B．n C．n(n-1)/2 D．n(n-1) 7. 从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 B. O(1) A. O(n) C. O(log2n) D. O(n2 ) 8. 由权值分别为 3,8,6,2 的四叶子结点生成一棵哈夫曼树，它的带权路径长度为 ( )。 A. 24 B. 38 C. 19 D. 35 9. 若根据数据集合{23,44,36,48,52,73,64,58}建立散列表，采用 h(K)=K%13 计算散列 地址，并采用链接法处理冲突，则元素 64 的散列地址为( )。 A. 4 B. 8 C. 12 D. 13 10. 在一棵 5 阶 B_树中，每个结点最多允许有（ ）个关键字。 A. 2 B. 3 C. 4 D. 5
二、填空题（每小题2分，共20分） 1.在结构中，前塑和后继结点之间存在着1对N的联系。 2在线性表的单替接存储中，假定每个结点的结构为(d妇ta,ext)。若一个结点的地址 为，则其后继结点的地址为 3.栈又称为 表，队列又称为先进先出表。 4,假定一棵树的广义表表示为A低C(I,JD,D(E,F,G),则树的深度为 5.在一棵几有1个结点的二叉树所对应的二叉蛙表中，必定包含有一个空指针。 6对于一个具有n个项点和。条边的连通图，存储它所用邻接表的空间复桑度为 7.在一个索引表中，每个索引项至少包含有索引值域和子表的 域这两项。 8.在线性表的存储中，无法查找到一个元素的前更或后鞋元素。 只在一棵B树中，所有 结点都处在月一层上。即最低层上。 10,在对个记录遗行堆排序的过程中，由初始堆到维排序结束，需要对树根结点进行 次棉运算。 三、运算愿（每小题6分，共24分） 1.假定一棵二叉树广文表表示为6(c),d(e,f(.》),试分别写出对它进行先序、中 序和后序遍历的结果。 先序： 中序： 后序： 2.已知一个图的顶点集V和边集G分别为： V-0,1,2.3,4,5副： E={0,1)80,2050,302,(1.5)6,(2.3)10,(2.4)13.35)91: 试写出按展普里傅算法从项点1出发得到最小生成树的过程中，依次选取的各条边，并 求出其最小生成树的权。 各条边： 最小生成树的权： 3已知一个图的顶点集V和边集G分别为： V=0,1,23,4,5.6 E=0,2>.1.3>,1.4>,,25>,,4,6>}: 2
2 二、填空题（每小题 2 分，共 20 分） 1. 在________结构中，前驱和后继结点之间存在着 1 对 N 的联系。 2. 在线性表的单链接存储中，假定每个结点的结构为(data,next)，若一个结点的地址 为 p，则其后继结点的地址为____________。 3．栈又称为________________表，队列又称为先进先出表。 4．假定一棵树的广义表表示为 A(B,C(I,J),D(E,F(H,G)))，则树的深度为________。 5．在一棵具有 n 个结点的二叉树所对应的二叉链表中，必定包含有________个空指针。 6. 对于一个具有 n 个顶点和 e 条边的连通图，存储它所用邻接表的空间复杂度为 ________。 7．在一个索引表中，每个索引项至少包含有索引值域和子表的___________域这两项。 8．在线性表的________存储中，无法查找到一个元素的前驱或后继元素。 9.在一棵 B_树中，所有____________结点都处在同一层上，即最低层上。 10. 在对 n 个记录进行堆排序的过程中，由初始堆到堆排序结束，需要对树根结点进行 _______次筛运算。 三、运算题（每小题 6 分，共 24 分） 1. 假定一棵二叉树广义表表示为 a(b(c),d(e,f(,g)))，试分别写出对它进行先序、中 序和后序遍历的结果。 先序： 中序： 后序： 2．已知一个图的顶点集 V 和边集 G 分别为： V={0,1,2,3,4,5}; E={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)10,(2,4)13,(3,5)9}; 试写出按照普里姆算法从顶点 1 出发得到最小生成树的过程中，依次选取的各条边，并 求出其最小生成树的权。 各条边：________, ________, ________, ________, ________。 最小生成树的权： 3. 已知一个图的顶点集 V 和边集 G 分别为： V={0,1,2,3,4,5,6} E={,,,,,,};
若存储它采用忽接表，并且每个晚点邻接表中的边结点都是按黑出边暖点序号从小到大 的次序链接的。则按属主教村中介锦的进行拓扑排序的算法，写出得到的拓扑序列。 拓扑序列： 4.有5个修权结点.其权值分别为3,7,2，&14，以它们为叶子结点生成一棵霍夫曼树， 求出该树的带权路径长度和树的高度。 带权路径长度 高度： 四、阅读算法，回答间题（每小题8分，共16分） 1.int AE(int a[].int n) if(n==0)return 0: else return a[n-1]+AE(a,n-1) 写出该递归算法的功隆： 2下面算法中的T指向一棵具有个元素的二叉树的根结点。 void preserve(BTreeNode*BT,EleaType al],int n) statie int i=0: if(BTI=MULL) preserve(BT->left,a.n): a[i++]=BT->data: preserve(BT->richt,a.n): 写出该递归算法的功陵： 五、算法填空，在西有横线的地方填写合适的内客（每小题6分，共12分） 【.向以ST为树根指针的二义搜索树上插入值为1tcm的精点的递归算法， void Insert (BTreeNode*BST,const EleType&item) if(sT-wL)（ BST=new BTreeNode:
3 若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照出边顶点序号从小到大 的次序链接的，则按照主教材中介绍的进行拓扑排序的算法，写出得到的拓扑序列。 拓扑序列： 4. 有 5 个带权结点，其权值分别为 3,7,2,6,14，以它们为叶子结点生成一棵霍夫曼树， 求出该树的带权路径长度和树的高度。 带权路径长度： 高度： 四、阅读算法，回答问题（每小题 8 分，共 16 分） 1. int AE(int a[], int n) { if(n==0) return 0; else return a[n-1]+AE(a,n-1); } 写出该递归算法的功能： 2. 下面算法中的 BT 指向一棵具有 n 个元素的二叉树的根结点。 void preserve(BTreeNode* BT, ElemType a[], int n) { static int i=0; if(BT!=NULL) { preserve(BT->left, a, n); a[i++]=BT->data; preserve(BT->right, a, n); } } 写出该递归算法的功能： 五、算法填空，在画有横线的地方填写合适的内容(每小题 6 分，共 12 分) 1. 向以 BST 为树根指针的二叉搜索树上插入值为 item 的结点的递归算法。 void Insert(BTreeNode*& BST, const ElemType& item) { if(BST==NULL) { BST=new BTreeNode;
BST->data"iten: BST->right-NULL: else if(itemBST->data)Insert (BST->left,item) else 2下面算法的功能为：根据BT所指的二叉树生成一绿新的二叉树并返回树根指针，新 二叉树是已知二叉树T中所有结点的左、右子树交换的结果。 BTreeNode*BTreeSwopX (BTreeNode*BT) if (BT--NULL)return else BTreeNode pt=new BTreeNode: pt->data= pt->left"BTreeSwopX(BT->right); pt->right■ return pt: 六、轴写算法（⑧分） 按所给函数声明编写一个算法，从表头指针为乱的单链表中查找出具有最大植的结点， 该最大值由函数返目，若单硫表为空则中止运行： ElenType MaxYalue(LNode*HL) 4
4 BST->data=item; ________________; BST->right=NULL; } else if(itemdata) Insert(BST->left, item); else ____________________________; } 2. 下面算法的功能为：根据 BT 所指的二叉树生成一棵新的二叉树并返回树根指针，新 二叉树是已知二叉树 BT 中所有结点的左、右子树交换的结果。 BTreeNode* BTreeSwopX(BTreeNode* BT) { if(BT==NULL) return ________; else { BTreeNode* pt=new BTreeNode; pt->data=______________; pt->left=BTreeSwopX(BT->right); pt->right=__________________________; return pt; } } 六、编写算法(8 分) 按所给函数声明编写一个算法，从表头指针为 HL 的单链表中查找出具有最大值的结点， 该最大值由函数返回，若单链表为空则中止运行。 ElemType MaxValue(LNode* HL);
答案供参者 一、单进题（每小题2分，共20分） 1.B2A3.A4.B5B 6B7.C8.D9.C10.C 二、填空题（每小题2分，共20分） 1.树 2.p->next 3后进先出 44 5n*1 6.0(n*e) 7.开始位置 8.酸列 9叶子 10.n-1 三、运算题（每小题6分，共24分） 1.先序1a,bC,dgf,8 1/2分 中序：c,b,a,e,dE,g 1/2分 后序：c,be,gf.d,a 1/2分 2(1.5)6,(1.008,(0,3)20,205,2.4)13 114分 最小生成树的权：3料 1/2分 3拓扑序列1,3,025,4.6 /6分，若仍为一种拓扑序列则得3分 4L带权路径长度：66 /4分 高度：5 /2分 四、阅读算法，园答问恩（每小愿8分，共16分） 评分标准：根据叙述完整程度的情给分。 1.算法功能：求出数组a中n个元素之和。 2算法功能，对具有个结点的由T指针所指向的二叉树选行中序着历，把得到的结 点值序列保存到数组ā中。 五、算法填空，在西有横战的地方填写合适的内容（郁小题6分，共12分） 1.BST->left=NULL 1/3分 Insert (BST->right.item) 1/3分 2ULBT->data BTree5sop或(BT->1eft)/每空2分 六、编写算法（⑧分） 评分标准：根据编程的完整程度的情给分，算法中给出了参考得分
5 答案供参考 一、单选题（每小题 2 分，共 20 分） 1. B 2. A 3. A 4. B 5. B 6. B 7. C 8. D 9. C 10. C 二、填空题（每小题 2 分，共 20 分） 1. 树 2. p->next 3. 后进先出 4. 4 5. n+1 6. O(n+e) 7.开始位置 8. 散列 9. 叶子 10. n-1 三、运算题（每小题 6 分，共 24 分） 1. 先序： a,b,c,d,e,f,g //2 分 中序： c,b,a,e,d,f,g //2 分 后序： c,b,e,g,f,d,a //2 分 2. (1,5)6, (1,0)8, (0,3)2, (0,2)5, (2,4)13 //4 分 最小生成树的权：34 //2 分 3. 拓扑序列：1,3,0,2,5,4,6 //6 分，若仍为一种拓扑序列则得 3 分 4. 带权路径长度：66 //4 分 高度：5 //2 分 四、阅读算法，回答问题（每小题 8 分，共 16 分） 评分标准：根据叙述完整程度酌情给分。 1. 算法功能：求出数组 a 中 n 个元素之和。 2. 算法功能：对具有 n 个结点的由 BT 指针所指向的二叉树进行中序遍历，把得到的结 点值序列保存到数组 a 中。 五、算法填空，在画有横线的地方填写合适的内容(每小题 6 分，共 12 分) 1. BST->left=NULL //3 分 Insert(BST->right, item) //3 分 2. NULL BT->data BTreeSwopX(BT->left) //每空 2 分 六、编写算法(8 分) 评分标准：根据编程的完整程度酌情给分，算法中给出了参考得分
ElemType MaxValue (LNode*B.) if (HL=NULL) 1/2分 cerrdata: /3分 LNode。p-l-next: ∥4分 while(p=N》《 if(maxdata)max=p->data: p-p->next: //7分 return max: /8分
6 ElemType MaxValue(LNode* HL) { if(HL==NULL) { //2 分 cerrdata; //3 分 LNode* p=HL->next; //4 分 while(p!=NULL) { if(maxdata) max=p->data; p=p->next; } //7 分 return max; //8 分 }