数据结构与程序设计Word文件下载.docx

1、 j+ ） cij=0.0; for （ int k = 1; k k+ ） cij = cij + aik * bkj; （2） x = 0; y = 0; for （ int i = 1; i+ ） for （ int j = 1;= i; j+ ） for （ int k = 1;= j; x = x + y;1.5 试计算以下求和程序中所有语句的总执行次数。float sum（ float a , int n ） float s = 0.0; for （ int i = 0; n; s += ai; return s;1.6 试用大O表示法给出下面程序的时间复杂性。void out （

2、 float x , int m, int n ） float sum ; m; i+ ） sumi = 0.0; for （ int j = 0; sumi = xij; cout Line: : sumi endl;第二章 数组2.1 判断下列叙述的对错。 （1） 线性表的逻辑顺序与物理顺序总是一致的。 （2） 线性表的顺序存储表示优于链式存储表示。 （3） 线性表若采用链式存储表示时所有存储单元的地址可连续可不连续。 （4） 二维数组是其数组元素为线性表的线性表。 （5） 每种数据结构都应具备三种基本运算：插入、删除和搜索。2.2 线性结构可用顺序表或链表存储。试问： （1） 如果有n个

3、表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？ （2） 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？2.3 已知整数数组A 中有n个元素，试设计一个算法，求数组中所有元素值的和。2.4 已知整数数组A 中有n个元素，试设计一个算法，求数组中所有元素值的平均值。2.5 设有一个线性表 （e0, e1, , en-2, en-1） 存放在一个一维数组AarraySize中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个地址的内容置换为 （en-

4、1, en-2, , e1, e0）。2.6 假定数组AarraySize中有多个零元素, 试写出一个函数, 将A 中所有的非零元素依次移到数组A的前端Ai （0 i link = p-link; p-link = s; （2） q- s-link = p; （3） p-link = s- （4） p-link = q;3.2 设单链表中结点的结构为（data, link）。已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列哪一个操作？ （2） s- （3） s- p = s; （4） p-3.3 设单链表中结点的结构为（data, link）。若想摘除结点*p的直接后继，则

5、应执行下列哪一个操作？ （1） p-link- （2） p = p- （4） p = p-3.4 已知head为单链表的表头指针, 链表中存储的都是整型数据，试写出实现下列运算的递归算法： （1） 求链表中的最大整数。 （2） 求链表的结点个数。3.5 设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。prh3.6 设A和B是两个单链表，表中的元素均按结点的值（整数）升序排列。试编写一个函数，将A和B归并成一个按结点的值降序排列的单链表C。要求辅助存储空间为O（1）。3.7 设单循环

6、链表中结点的结构为（data, link），且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪一个操作？（1） s = rear; rear = rear- free（s）;（2） rear = rear- free（rear）;（3） rear = rear- （4） s = rear- rear-3.8 有一个循环链表，它既没有头指针又没有头结点。只有一个指针p指向表中的某一结点。试编写一个函数，删除指针p所指结点的直接前驱结点。3.9 判断一个带表头结点的双向循环链表L是否对称相等的算法如下所示，请在算法中的 处填入正确的语句。 int s

7、ymmetry （ DlinkList L ） int sym = 1; DlistNode * p = L-next, q = L-prior; while （ （ p != q | p-prior = q ） & ） if （ p-data = q-data ） ; ; else sym = 0; return sym;3.10 设双向循环链表中结点的结构为（data, prior, next），且不带表头结点。若想在指针p所指结点之后插入指针s所指结点，则应执行下列哪一个操作？（1） p-next = s;prior = p;next-prior = s;next = p-next;（2

8、） p-（3） s-（4） s-3.11 试设计一个实现下述要求的查找运算函数Locate（L, x）。设有一个带表头结点的双向链表L，每个结点有4个数据成员：指向前驱结点的指针prior、指向后继结点的指针next、存放数据的成员data和访问频度freq。所有结点的freq初始时都为0。每当在链表上进行一次Locate （L, x）操作时，令元素值为x的结点的访问频度freq加1，并将该结点前移，链接到与它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。第四章 栈和队列4.1 试回答下列问题： （1） 设整数1, 2, 3, 4,

9、5, 6依次进栈，则可能的出栈序列有多少种? （2） 若整数1, 2, 3, 4, 5, 6依次进栈，那么是否能够得到435612, 325641, 154623和135426的出栈序列。 4.2 设有一个顺序栈S，元素s1, s2, s3, s4, s5, s6依次进栈，如果6个元素的出栈顺序为s2, s3, s4, s6, s5, s1，则顺序栈的容量至少应为多少？4.3 设顺序栈S的元素个数最大为MaxSize。试改写顺序栈的进栈函数Push （S, x），要求当栈满时执行一个stackFull（S） 操作进行栈满处理。其功能是：动态创建一个比原来的栈元素存放数组大二倍的新数组，代替原来

10、的栈元素存放数组，原来栈元素存放数组中的元素占据新数组的前MaxSize位置。4.4 设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想在链式栈的栈顶插入一个由指针s所指的结点，则应执行下列哪一个操作？（1） top- （2） s-link = top- top-link = top; top = s; （4） s- top = top-4.5 设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到x中，则应执行下列哪一个操作？（1） x = top-data; （2） top = top- x

11、= top-（3） x = top; （4） x = top-4.6 假设以数组Qm存放循环队列中的元素, 同时以rear和length分别指示循环队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件, 并写出相应的插入（EnQueue）和删除（DlQueue）元素的操作。4.7 假设以数组Qm存放循环队列中的元素, 同时设置一个标志tag，以tag = 0和tag = 1来区别在队头指针（front）和队尾指针（rear）相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入（EnQueue）和删除（DlQueue）的函数。4.8 若使用循环链表来表示队列，p是

12、链表中的一个指针（视为队尾指针）。试基于此结构给出队列的插入（EnQueue）和删除（DlQueue）的函数，并给出p为何值时队列空。第六章 树与森林6.1 一棵具有n个结点的理想平衡二叉树（即除离根最远的最底层外其他各层都是满的，最底层有若干结点）有多少层？若设根结点在第0层，则树的高度如何用n来表示（注意n可能为0）？6.2 n个结点可构造出多少种不同形态的二叉树? 若有3个数据1, 2, 3，输入它们构造出来的中序遍历结果都为1, 2, 3的不同二叉树有哪些?6.3 假定在一棵二叉树中，度为2 的结点有15个，度为1的结点有20个，试问度为0的结点有多少个？6.4 判断下列叙述的对错。

13、（1） 二叉树是树的特殊情形。 （2） 若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点。 （3） 若有一个结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。（4） 若有一个叶子结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点。（5） 若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。6.5 试分别画出满足以下条件的所有二叉树： （1） 二叉树的前序序列

14、与中序序列相同； （2） 二叉树的中序序列与后序序列相同； （3） 二叉树的前序序列与后序序列相同。6.6 已知一棵二叉树的前序遍历结果是ABECDFGHIJ, 中序遍历结果是EBCDAFHIGJ, 试画出这棵二叉树。6.7 若用二叉链表作为二叉树的存储表示，试编写一个递归算法求二叉树中指定结点所在层次。（设二叉树的高度为h，空树时h = -1，只有一个结点的二叉树的高度为h = 0）6.8 已知一棵完全二叉树存放于一个一维数组Tn中，Tn中存放的是各结点的值。试设计一个算法，从T0开始顺序读出各结点的值，建立该二叉树的二叉链表表示。6.9 下面是一个二叉树的前序遍历的递归算法。 void P

15、reOrder （ BinTreeNode *t ） if （ t != NULL ） /递归结束条件 t- /访问（输出）根结点 PreOrder （ t-leftChild ）; /前序遍历左子树rightChild ）; /前序遍历右子树（1） 改写PreOrder算法，消去第二个递归调用PreOrder （t-（3） 利用栈改写PreOrder算法，消去两个递归调用。6.10 设二叉树采用二叉链表表示，指针root指向根结点，指针p指向二叉树中某一指定结点。试编写一个算法，找出从根结点到结点*p之间的路径。6.11 从供选择的答案中选择与下面有关二叉树和森林的叙述中各括号相匹配的词句，

16、将其编号填入相应的括号内。 （1） 设二叉树有n个结点且根结点处于第0层，则其高度为（ A ）。 （2） 设高度为h（空二叉树的高度为-1，只有一个结点的二叉树的高度为0）的二叉树只有度为2和度为0的结点，则该二叉树中所含结点至少有（ B ）个。 （3） 设森林F中有4棵树，第1、2、3、4棵树的结点个数分别为n1、n2、n3、n4，当把森林F转换成一棵二叉树后，其根结点的右子树中有（ C ）个结点。 （4） 设森林F中有4棵树，第1、2、3、4棵树的结点个数分别为n1、n2、n3、n4，当把森林F转换成一棵二叉树后，其根结点的左子树中有（ D ）个结点。（5） 将含有82个结点的完全二叉树从

17、根结点开始顺序编号，根结点为第0号，其他结点自上向下，同一层自左向右连续编号。则第40号结点的双亲结点的编号为（ E ）。【供选择的答案】A： n-1 log2（n+1） -1 log2n +1 不确定B： 2h 2h -1 2h +1 h +1CD： n1-1 n1+n2+n3 n2+n3+n4 n1E： 20 19 81 806.12 一棵高度为h的满k叉树有如下性质: 第h层上的结点都是叶结点, 其余各层上每个结点都有k棵非空子树, 如果按层次自顶向下, 同一层自左向右, 顺序从1开始对全部结点进行编号, 试问: （1） 各层的结点个数是多少? （2） 编号为i的结点的父结点（若存在）的

18、编号是多少? （3） 编号为i的结点的第m个孩子结点（若存在）的编号是多少? （4） 编号为i的结点有右兄弟的条件是什么? 其右兄弟结点的编号是多少? （5） 若结点个数为 n, 则高度h是n 的什么函数关系?6.13 判断以下序列是否是最小堆? 如果不是, 将它调整为最小堆。 （1） 100, 86, 48, 73, 35, 39, 42, 57, 66, 21 （2） 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 6.14 给定权值集合 15, 03, 14, 02, 06, 09, 16, 17 , 构造相应的Huffman树, 并计算它的带权外部路径长度

19、。6.15 假定用于通信的电文仅由8个字母c1, c2, c3, c4, c5, c6, c7, c8组成, 各字母在电文中出现的频率分别为5, 25, 3, 6, 10, 11, 36, 4。试为这8个字母设计不等长Huffman编码, 并给出该电文的总码数。第七章 集合与搜索7.1 供选择的答案中选择与下面有关搜索算法的叙述中各括号相匹配的词句，将其编号填入相应的括号内。 （1） 对线性表进行折半搜索时，要求线性表必须（ A ）。 （2） 采用顺序搜索算法查找长度为n的线性表时，元素的平均搜索长度为（ B ）。 （3） 采用折半搜索算法查找长度为n的线性表时，元素的平均搜索长度为（ C ）

20、。（4） 折半搜索与二叉搜索树（即二叉排序树）的时间性能（ D ）。（5） 顺序搜索算法适合于存储结构为（ E ）的线性表。 以数组方式存储 以数组方式存储且结点按关键码有序排列 以链接方式存储 以链接方式存储且结点按关键码有序排列 n/2 n （n+1）/2 （n-1）/2C： O（n2） O（nlog2n） O（log2n） O（n）D： 相同 不相同 散列存储 顺序存储或链接存储 压缩存储 索引存储7.2 设有序顺序表中的元素依次为017, 094, 154, 170, 275,503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行顺序搜索

21、时的判定树, 并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。7.3 设有序顺序表中的元素依次为017, 094, 154, 170, 275,503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行折半搜索时的判定树, 并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。7.4 设有一个关键码序列 DEC, FEB, NOV, OCT, JUL, SEP, AUG, APR, MAR, MAY, JUN, JAN（1） 按字母顺序依次插入到一棵初始为空的AVL树中，画出每插入一个关键码后的AVL树，并标明平衡旋转的类型。 （2） 从所建立的AVL树中删除关键码MAY，为保持AVL树的特性，应如何进行删除和调整? 若接着删除关键码FEB，又应如何删除与调整?7.5 设有一个关键码的输入序列 55, 31, 11, 37, 46, 73, 63, 02, 07 , （1） 从空树开始构造平衡二叉搜索树, 画出每加入一个新结点时二叉树的形态。若发生不平衡, 指明需做的平衡旋转的类型及平衡旋转的结果。 （2） 计算该平衡二叉搜索树在等概率下的查找成功的平均查找长度和查找不成功的平均查找长度。7.6 对于一个高度为h的AVL树，其最少结点数是多少？反之，