习题一
1.什么是数据结构，数据的逻辑结构，数据的存储结构？数据结构对算法有什么影响？请举例说明。
2.数据结构的存储方式主要有哪两种？它们之间的本质区别是什么？
3.设n为正整数, 分析下列各程序段中加下划线的语句的执行次数。
(1)    for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) {
            c[i][j] = 0.0;
            for (int k = 1; k <= n; k++)
                    c[i][j] = c[i][j] + a[i][k] * b[k][j];
}
(2)    x = 0;  y = 0;
    for (int i = 1; i <= n; i++)     
            for (int j = 1; j <= i; j++)
            for (int k = 1; k <= j; k++)
                  x = x + y;
(3)    int i = 1,  j = 1;
      while (i<=n && j<=n) {
          i = i + 1;  j = j + i;
      }
(4)*    int i =1;
      do{
            for (int j = 1; j <= n; j++)
              i = i + j;
      }while(i<100 + n);
4.试编写一个函数计算n!*2n的值，结果存放于数组A[arraySize]的第n个数组元素中，0 ≤ n ≤ arraySize。若设计算机中允许的整数的最大值为maxInt，则当n>arraySize或者对于某一个k (0 ≤ k ≤ n)，使得k!*2k > maxInt时，应按出错处理。可有如下三种不同的出错处理方式：
    (1) 用printf显示错误信息及exit(1)语句来终止执行并报告错误；
    (2) 用返回整数函数值0, 1来实现算法，以区别是正常返回还是错误返回；
    (3) 在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种错误返回。
    试讨论这三种方法各自的优缺点，并以你认为是最好的方式实现它。
5.设有一个线性表 (a0, a1, …, an-2, an-1) 存放在一个一维数组A[arraySize]中的前n个数组
元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个原址内容置换为 (an-1, an-2, …, a1, a0)。最后分析此算法的时间复杂度及空间复杂度。
6.顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下, 对有127个元素的顺序表进行插入, 平均需要移动多少个元素? 删除一个元素, 又平均需要移动多少个元素?
7.利用顺序表的操作，实现以下的函数。并分析你所编制的函数的时间复杂度，并分析(2)与(3)的时间复杂度出现差异的原因。
    (1) 从顺序表中删除具有给定值x的所有元素。
    (2) 从顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素。
    (3) 从有序顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素。
    (4) 将两个有序顺序表la,lb合并成一个新的有序顺序表lc。
    (5) 从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。
8.线性表可用顺序表或链表存储。试问：
    (1) 两种存储表示各有哪些主要优缺点?
    (2) 如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？
    (3) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？
9.试写出计算线性链表长度的算法。
10.设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。
11.设有一线性链表，其结点值均为整数。试将该线性链表分解为两个线性链表，其中一链表中的结点值均为负整数，而另一链表中结点的值均为正整数，并删除结点值为零的结点。
12．设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针, 试设计一个算法, 将这两个有序链表合并成一个非递减有序的单链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。
13．设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针, 试设计一个算法, 将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。
14.在一个循环链表中寻值为x的结点，并将该结点移到第一个结点之前。
15.对于下面的每一步，画出栈元素和栈顶指针的示意图：
（1）栈初始化；
（2）元素x入栈；
（3）元素y入栈；
（4）出栈
（5）栈初始化
（6）元素z入栈
16.铁路进行列车调度时, 常把站台设计成栈式结构的站台，如右图所示。试问：
    (1) 设有编号为1,2,3,4,5,6的六辆列车, 顺序开入栈式结构的站台, 则可能的出栈序列有多少种?
    (2) 若进站的六辆列车顺序如上所述, 那么是否能够得到435612, 325641, 154623和135426的出站序列, 如果不能, 说明为什么不能; 如果能, 说明如何得到(即写出"进栈"或"出栈"的序列)。
17.试证明：若借助栈可由输入序列1, 2, 3, …, n得到一个输出序列p1, p2, p3, …, pn (它是输入序列的某一种排列)，则在输出序列中不可能出现以下情况，即存在i < j < k，使得pj < pk < pi。(提示：用反证法)
18.将编号为0和1的两个栈存放于一个数组空间V[m]中，栈底分别处于数组的两端。当第0号栈的栈顶指针top[0]等于-1时该栈为空，当第1号栈的栈顶指针top[1]等于m时该栈为空。两个栈均从两端向中间增长。当向第0号栈插入一个新元素时，使top[0]增1得到新的栈顶位置，当向第1号栈插入一个新元素时，使top[1]减1得到新的栈顶位置。当top[0]+1 == top[1]时或top[0] == top[1]-1时，栈空间满，此时不能再向任一栈加入新的元素。试定义这种双栈(Double Stack)结构的类定义，并实现判栈空、判栈满、插入、删除算法。
19.改写顺序栈的进栈成员函数Push(x)，要求当栈满时执行一个stackFull( )操作进行栈满处理。其功能是：动态创建一个比原来的栈数组大二倍的新数组，代替原来的栈数组，原来栈数组中的元素占据新数组的前MaxSize位置。
20.根据教案中给出的优先级，回答以下问题：
    (1) 在表达式求值的过程中，如果表达式e含有n个运算符和分界符，问操作数栈(NS)中最多可存入多少个元素？
    (2) 如果表达式e含有n个运算符，且括号嵌套的最大深度为6层，问栈中最多可存入多少个元素？
21.表达式的中缀表示为a * x - b / x^2，试利用栈将它改为后缀表示ax * bx2^/ -。写出转换过程中栈的变化。(^表示乘方运算)
22.设循环队列的容量为70（序号从1到70），经过一系列入队和退队运算后，有：
（1）front=15，rear=46；
（2）front=45，rear=10
问在上述两种情况下，循环队列中各有多少个元素？
23.设用链表表示一个双端队列，要求可在表的两端插入，但限制只能在表的一端删除。试编写基于此结构的队列的插入(enqueue)和删除(dequeue)算法，并给出队列空和队列满的条件。
                            习题2
1．列出右图所示二叉树的叶结点、分支结点和每个结点的层次。
2．使用 (1) 顺序表示和 (2) 二叉链表表示法，分别画出上图所示二叉树的存储表示。
3．在结点个数为n (n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？
4．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。
5．如果一棵树有n1个度为1的结点, 有n2个度为2的结点, … , nm个度为m的结点, 试问有多少个度为0的结点? 试推导之。
6．若用二叉链表作为二叉树的存储表示，试针对以下问题编写递归算法：
(1) 统计二叉树中叶结点的个数。
数据结构与算法分析答案(2) 以二叉树为参数，交换每个结点的左子女和右子女。
(3) 求二叉树的深度。
7．一棵高度为h的满k叉树有如下性质: 第h层上的结点都是叶结点, 其余各层上每个结点都有k棵非空子树, 如果按层次自顶向下, 同一层自左向右, 顺序从1开始对全部结点进行编号, 试问:
    (1) 各层的结点个数是多少?
    (2) 编号为i的结点的父结点(若存在)的编号是多少?
    (3) 编号为i的结点的第m个孩子结点(若存在)的编号是多少?
    (4) 编号为i的结点有右兄弟的条件是什么? 其右兄弟结点的编号是多少?
    (5) 若结点个数为 n, 则高度h是n 的什么函数关系?
8．请画出下图所示的树所对应的二叉树。
1
2
3
4
5
6
7
8
9．已知一棵二叉树的前序遍历的结果是ABECDFGHIJ, 中序遍历的结果是EBCDAFHIGJ, 试画出这棵二叉树。
10．给定权值集合{15, 03, 14, 02, 06, 09, 16, 17}, 构造相应的霍夫曼树, 并计算它的带权路径长度。
习题三
1. 设有序顺序表中的元素依次为017, 094, 154, 170, 275, 503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行折半查时的二叉查树, 并计算查成功的平均查长度和查不成功的平均查长度。
2. 若对有n个元素的有序顺序表和无序顺序表进行顺序查, 试就下列三种情况分别讨论两者在等查概率时的平均查长度是否相同?
(1) 查失败;
(2) 查成功, 且表中只有一个关键码等于给定值k的对象;
(3) 查成功, 且表中有若干个关键码等于给定值k的对象, 要求一次查出所有对象。
3. 设有10000个记录对象, 通过分块划分为若干子表并建立索引, 那么为了提高查效率, 每一个子表的大小应设计为多大?

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。