1、第 1 章 绪论5选择题：CCBDCA6试分析下面各程序段的时间复杂度。（1）O（1）（2）O（m*n）（3）O（n 2）（4）O（log 3n）（5）因为 x+共执行了 n-1+n-2+1= n(n-1)/2，所以执行时间为 O（n 2）（6）O( )第 2 章 线性表1选择题babadbcabdcddac2算法设计题（6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。ElemType Max (LinkList L )if(L-next=NULL) return NULL;pmax=L-next; /假定第一个结点中数据具有最大值p=L-next-next;while(p != N
2、ULL )/如果下一个结点存在if(p-data pmax-data) pmax=p;p=p-next;return pmax-data;（7）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。void inverse(LinkList L-next=NULL;while ( p) q=p-next; / q 指向*p 的后继p-next=L-next;L-next=p; / *p 插入在头结点之后p = q;（10）已知长度为 n 的线性表 A 采用顺序存储结构，请写一时间复杂度为 O(n)、空间复杂度为 O(1)的算法，该算法删除线性表中所有值为 item
3、的数据元素。题目分析 在顺序存储的线性表上删除元素，通常要涉及到一系列元素的移动（删第i 个元素，第 i+1 至第 n 个元素要依次前移） 。本题要求删除线性表中所有值为 item 的数据元素，并未要求元素间的相对位置不变。因此可以考虑设头尾两个指针（i=1，j=n） ，从两端向中间移动，凡遇到值 item 的数据元素时，直接将右端元素左移至值为 item 的数据元素位置。void Delete（ElemType A ，int n）A 是有 n 个元素的一维数组，本算法删除 A 中所有值为 item 的元素。i=1；j=n；设置数组低、高端指针（下标） 。while（itemplate cla
4、ss Queue /循环队列的类定义public: Queue ( int=10 );Queue ( ) delete Q; void EnQueue ( Type Type DeQueue ( );Type GetFront ( );void MakeEmpty ( ) front = rear = tag = 0; /置空队列int IsEmpty ( ) const return front = rear /判队列空否int IsFull ( ) const return front = rear /判队列满否private:int rear, front, tag; /队尾指针、队头指
5、针和队满标志Type *Q; /存放队列元素的数组int m; /队列最大可容纳元素个数构造函数template Queue: Queue ( int sz ) : rear (0), front (0), tag(0), m (sz) /建立一个最大具有 m 个元素的空队列。Q = new Typem; /创建队列空间assert ( Q != 0 ); /断言: 动态存储分配成功与否插入函数template void Queue : EnQueue ( Type /判队列是否不满，满则出错处理rear = ( rear + 1 ) % m; /队尾位置进 1, 队尾指针指示实际队尾位置Qr
6、ear = item; /进队列tag = 1; /标志改 1，表示队列不空删除函数template Type Queue : DeQueue ( ) assert ( ! IsEmpty ( ) ); /判断队列是否不空，空则出错处理front = ( front + 1 ) % m; /队头位置进 1, 队头指针指示实际队头的前一位置tag = 0; /标志改 0, 表示栈不满return Qfront; /返回原队头元素的值读取队头元素函数template Type Queue : GetFront ( ) assert ( ! IsEmpty ( ) ); /判断队列是否不空，空则出错
7、处理return Q(front + 1) % m; /返回队头元素的值第 4 章 串、数组和广义表1选择题BBCAB BBCBB ABDCB C2.综合应用题（1）已知模式串 t=abcaabbabcab写出用 KMP 法求得的每个字符对应的 next 和nextval 函数值。模式串 t 的 next 和 nextval 值如下：j 1 2 3 4 5 6 7 8 9 10 11 12 t 串 a b c a a b b a b c a bnextj 0 1 1 1 2 2 3 1 2 3 4 5nextvalj 0 1 1 0 2 1 3 0 1 1 0 5（3）数组 A 中，每个元素
8、Ai,j的长度均为 32 个二进位,行下标从-1 到 9，列下标从 1 到 11，从首地址 S 开始连续存放主存储器中，主存储器字长为 16 位。求： 存放该数组所需多少单元？ 存放数组第 4 列所有元素至少需多少单元？ 数组按行存放时，元素 A7,4的起始地址是多少？ 数组按列存放时，元素 A4,7的起始地址是多少？每个元素 32 个二进制位，主存字长 16 位，故每个元素占 2 个字长，行下标可平移至1 到 11。（1）242 （2）22 （3）s+182 （4）s+142(4)请将香蕉 banana 用工具 H( )Head( )，T( )Tail( )从 L 中取出。L=(apple,
9、(orange,(strawberry,(banana),peach),pear)H（H（T（H（T（H（T（L） ） ） ） ） ） ）（5）写一个算法统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为 A-Z 这 26 个字母和 0-9 这 10 个数字）。void Count（）/统计输入字符串中数字字符和字母字符的个数。int i，num36；char ch；for（i0；ilchild=NULL /判断该结点是否是叶子结点（左孩子右孩子都为空） ，若是则返回 1elsereturn LeafNodeCount(T-lchild)+LeafNodeCount
10、(T-rchild);（ 3） 交换二叉树每个结点的左孩子和右孩子。void ChangeLR(BiTree if(T-lchild=NULLelsetemp = T-lchild;T-lchild = T-rchild;T-rchild = temp;ChangeLR(T-lchild);ChangeLR(T-rchild);第 6 章 图1 选 择 题CBBBCBABAADCCDDB2应用题（ 1） 已 知 如 图 6.27 所 示 的 有 向 图 ， 请 给 出 ： 每个顶点的入度和出度； 邻接矩阵； 邻接表； 逆邻接表。 （ 2） 已 知 如 图 6.28 所 示 的 无 向 网 ，
11、请 给 出 ： 邻接矩阵； 邻接表； 最小生成树a b 4 c 3b a 4 c 5 d 5 e 9 c a 3 b 5 d 5 h 5 d b 5 c 5 e 7 f 6 g 5 h 4e b 9 d 7 f 3 f d 6 e 3 g 2 g d 5 f 2 h 6 h c 5 d 4 g 6 图 6.28 无向网6452379554（ 3） 已知图的邻接矩阵如 6.29 所 示 。试分别画出自顶点 1 出发进行遍历所得的深度优先生成树和广度优先生成树。（4）有向网如图 6.29 所 示 ，试用迪杰斯特拉算法求出从顶点 a 到其他各顶点间的最短路径，完成表 6.9。 D终点i=1 i=2
12、i=3 i=4 i=5 i=6b 15(a,b)15(a,b)15(a,b)15(a,b)15(a,b)15(a,b)c 2(a,c)d 12(a,d)12(a,d)11(a,c,f,d)11(a,c,f,d)e 10(a,c,e)10(a,c,e)f 6(a,c,f)g 16(a,c,f,g)16(a,c,f,g)14(a,c,f,d,g)S终点集a,c a,c,f a,c,f,e a,c,f,e,d a,c,f,e,d,g a,c,f,e,d,g,b图 6.29 邻接矩阵第 7 章 查找1 选 择 题CDCABCCCDCBCADA2应用题（ 1） 假定对有序表：（3，4，5，7，24，30
13、，42，54，63，72，87，95）进行折半查找，试回答下列问题： 画出描述折半查找过程的判定树； 若查找元素 54，需依次与哪些元素比较？ 若查找元素 90，需依次与哪些元素比较？ 假定每个元素的查找概率相等，求查找成功时的平均查找长度。先画出判定树如下（注：mid=(1+12)/2=6）：305 633 7 42 874 24 54 72 95查找元素 54，需依次与 30, 63, 42, 54 元素比较；查找元素 90，需依次与 30, 63,87, 95 元素比较；求 ASL 之前，需要统计每个元素的查找次数。判定树的前 3 层共查找12243=17 次；但最后一层未满，不能用 8
14、4，只能用 54=20 次，所以 ASL1/12（1720） 37/123.08（ 2） 在一棵空的二叉排序树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉排序树。127 172 11 16 21 4 9 13验算方法： 用中序遍历应得到排序结果： 2,4,7,9,11,12,13,16,17，21（ 5） 设哈希表的地址范围为 017，哈希函数为：H （key）=key%16。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49） ，构造哈希表，试回答下列问题： 画出哈希表的示意图； 若查找关键字 63，需要依次与哪些关键字进行比较？ 若查找关键字 60，需要依次与哪些关键字比较？ 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。画表如下：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1732 17 63 49 24 40 10 30 31 46 47查找 63,首先要与 H(63)=63%16=15 号单元内容比较，即 63 vs 31 ,no;
