号学 名姓 纸 卷 试 试 考 级学班 大 业 工 南 湖 称名程课 )院(系课程名称：数据结构 ( A卷 闭卷) 7．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执 行( )。 适用专业年级：计本09级 软件09 通信09级 网络工程09级 A．q->next＝p->next；p->next＝q； B．p->next＝q->next；q＝p； 考试时间: C．q->next＝p->next；p->next＝q； D．p->next＝q->next；q->next＝p； 100分钟 8．在一个顺序队列中，队首指针指向队首元素的( B )位置。 题号 一 二 三 四 五 六 七 八 九 十 总分 A．后一个 B．前一个 C．当前 统分人 9．向二叉搜索树中插入一个元素时，其时间复杂度大致为( v )。 题分 24 20 21 10 10 15 100 签名 A．O(㏒2n) B．O(n) C．O(1) D．O(㏒n2) 得分 10．执行下面程序段时，执行S语句的次数为( D )。 for(i=1;i<=n;i++) 考生注意事项：1、本试卷共 3 页，试卷如有缺页或破损，请立即举手报告以便更换。 2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。(答案请写在密封 for(j=1;j<=i;j++) S; 线内和纸卷正面，否则不记分) A .n*n B.n*n/2 C.n(n+1) D.n(n+1)/2 11. 设有两个串p和q，求q在p中首次出现的位置的算法称为( C )。 一、单项选择题(每个选项 1.5 分，共 24 分) 线A．求子串 B．联接 C．模式匹配 D．求串长 封密1．在一个长度为n的顺序存储的线性表中，删除第 i个元素（1≤i≤n≤n+1)时，需12. 已知广义表: A=(a,b), B=(A,A), C=(a,(b,A),B), 求下列运算的结果: 要从前向后依次前移( )个元素。 tail(head(tail(C))) =( F F )。 A．n-i B．n-i+1 C. n-i-1 D. i A.(a) B. A C. a D. (b) E. b F. (A) 2．在广义表的存储结构中，每个结点包含有( )个域。 13. 已知串S=‘aaab’,在KMP算法中其Next数组值为( A )。 A．1 B．2 C．3 D．4 A．0123 B．1123 C．1231 D．1211 3．若让元素1，2，3，4，5，6依次进栈，则出栈次序不可能出现的是( B )情况。 14. 将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，A. 325641 B. 154623 C. 135426 D. 654321 根结点编号为1，则编号为19的结点的右孩子的编号为( )。 4. 关键路径是事件结点网络中( )。 A. 38 B. 99 C. 39 D. 50 A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 15. 下面关于二分查找的叙述正确的是( C );在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，C．最长回路 D．最短回路 用二分折半法查找关键码值11，需做的关键码比较次数为( A ). 5. 假设以行序为主序存储二维数组A=array[1..100][1..100]，设每个数据元素占2（1）A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 个存储单元，基地址为10，则LOC[5，5]=( )。 B. 表必须有序，而且只能从小到大排列 A. 808 B. 818 C. 1010 D. 1020 C. 表必须有序且表中数据必须是整型，实型或字符型 6．若需要利用形参直接访问实参，则应把形参变量说明为( B )参数。 D. 表必须有序，且表只能以顺序方式存储 A．指针 B．引用 C．值 （2）A. 3 B. 4 C. 5 D. 6 第 1 页 共 3 页

号学 名姓 纸 卷 答 试 考 级学班 大 业 工 南 湖 称名程课 )院 ( 系 二、填空题(每空1分，共20分) 2．已知一个AOV网的邻接表表示如下所示(顶点为V0,V1,V2,V3,V4,V5)，请按照教材上给出的1．在线性表的顺序存储结构中，若一个元素所在结点的地址为P，则其后继结点的地拓扑排序算法，写出此AOV网的拓扑序列。 址为 。 2. 在线性表的单链表存储结构中，若一个元素所在结点的地址为P，则其后继结点的地址为 。 3．在以HL为表头指针的带表头附加结点的单链表和循环单链表中，链表为空的条件分别为 和 。 4.在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素 、 和元素的值三项。 5．队列的插人操作在 进行，删除操作在 进行。 6．操作数是一位正整数的后缀表达式“79*45+-”的值为 。 7．在一棵三叉树中，度为3的结点数有1个，度为2的结点数有2个，度为1的结点3．假定一个待散列存储的线性表(32,75,29,63,48,94,25,36,18,70)散列地址空间HT[11]，若采用除数为2个，那么度为0的结点数有 个。 留余数法构造散列函数，处理冲突用线性探查法，试画出最后得到的散列表。 线 设散列表为： 封8．若对一棵二又树从0开始进行结点编号，并按此编号把它顺序存储到一维数组a密中，则 a[i]元素的左孩子元素为 ，右孩子元素为 ，双亲元素0 1 2 3 4 5 6 7 8 9 10 （i＞0）为 。 70 18 25 48 36 94 29 63 75 32 9．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定 该四、阅读算法题(每题5分，共10分) 结点的值，右子树上所有结点的值一定 该结点的值。 10．以顺序查找方式从长度为n的线性表中查找一个元素时，平均查找长度1． void AD(LNode * & HL) 为 ，时间复杂度为 。 { Insert(HL，30)； //前插方法 11．以M分查找方法在一个线性表中进行查找时，此线性表必须是 存储 Insert(HL，50)； 的 表。 Delete(HL，26)； 12．在堆排序的过程中，对任一分支结点进行筛选运算的时间复杂度为 。 Delete(HL，55)； } 三、运算题(每小题7分，共21分) 假定调用该算法时以HL为表头指针的单链表中的内容为(15，26，48，55)，则调用返回后该单1．有七个带权结点，其权值分别为2,9,8,4,10,12,16,试以它们为叶子结点构造一棵哈夫链表中的内容变为：50 30 15 48 曼树，并计算出带权路径长度WPL。 第

2 页 共 3 页

2．现有一个二叉树的算法如下： int test2 (BtreeNode * BT) { if (BT = =NULL) return 0; else { int h1=test2 (bt->left); int h2=test2 (bt->right); if (h1>h2) return h1+1; else return h2+1; } } 此算法的功能是： 六、算法设计题(共15分) 1. 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递增次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。（该题9分） 假定该算法的数据结构如下： typedef struct Lnode{ int data; struct Lnode *next; } *LinkList; 假定该算法的函数头为：LinkList MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc） //已知单链表La 和 Lb 的元素按值递增排列，La和 Lb分别是指向两个链表头结点的头指针，算法返回指向归并后的单链表头指针Lc。 2. 已知奇偶交换排序算法描 述如下：第一趟对所有奇数i，将a[i]和a[i+1]进行比较，第二趟对所有偶数i，将a[i]和a[i+1]进行比较，每次比较时若a[i]>a[i+1]，则将两者交换，以后重复上述两趟过程，直到整个数组有序。编写一个实现上述排序过程的算法。（该题6分） 五、构造题 (10分) 已知世界六大城市为：北京(Pe)、纽约(N)、巴黎(Pa)、伦敦(L)、东京(T)、墨西哥(M)，下表给定了这六大城市之间的交通里程，要求按此表完成： （1） 画出这六大城市的交通网络图。 （2） 画出该图的邻接表表示法以及基于该邻接表的深度优先序列（假定邻接表中邻接点的编号按从小到大排列，并且遍历起始顶点为PE）。 （3） 画出该图的最小生成树 （不必写出构建过程）。 世界六大城市交通里程表(单位:百公里) PE N PA L T M PE 109 82 81 21 124 N 109 58 55 108 32 PA 82 58 3 97 92 L 81 55 3 95 89 T 21 108 97 95 113 M 124 32 92 89 113 解答 第 3 页 共 3 页