1.数据结构中，与所使用的计算机无关的是数据的__结构

  • [ ] 存储
  • [ ] 物理
  • [x] 逻辑
  • [ ] 物理和逻辑

2.计算机算法必须具备输入，输出和__等5个特性

  • [ ] 可行性，可移植性和可扩充性
  • [x] 可行性，确定性和有穷性
  • [ ] 确定性，有穷性和稳定性
  • [ ] 易读性，稳定性和安全性

3.顺序表表，链表的特点

  • 顺序表是顺序存储，在存储的时候，插入和删除需要移动插入和删除点后面的数据，不方便
  • 在n个节点的顺序表上做插入，删除节点运算的时间复杂度为O(n)，在长度为n的顺序表的第i个位置上插入一个元素，元素的移动次数是O(n-i+1).拥有n个元素的顺序表中插入一个新元素，平均移动n/2个元素
  • 线性表中节点的集合是有限的，节点之间的关系是一对一的
  • 顺序表可以直接对节点进行存取，不需要访问之前的节点，所以于顺序表的长度N无关，因此在顺序表中访问任一节点的时间复杂度为O(1)
  • 链表中的节点可包含多个指针域，分别存放多个指针。例如双向链表中的节点含有两个指针，分别存放其直接前驱和直接后继节点的指针
  • 链表的存储特点是无序，而链表示意图有序。
  • 链表的节点不会移动，只是指针内容改变
  • 顺序存储方式不仅用于存储线性结构还可以存储非线性结构，例如完全二叉树
  • 在顺序表中访问第i个节点和求第i个节点的直接前驱算法时间复杂度为O(1),所以若线性表最常用的操作是存取第i个元素及其前驱的值，则采用顺序表的存储方式
  • 单链表的存储密度小于1
  • 链表不具有的特点是：不可以随机访问任一元素，不适用于随机存取，所以顺序表相对于链表优点是，存储密度高和随机存储
  • 在某链表中最常用的操作是在最后一个节点之后插入一个节点和删除最后一个节点，则采用带头节点的双循环链表
  • 带头节点的单链表为空的条件是head->next=NULL，因为head指向头节点，head->next指向第一个元素节点，head->next==NULL代表该单链表为空.在单链表中，增加头节点的目的是为了方便运算的实现

4.栈和队列的特点

  • 队列中的元素个数是可变的

  • 队列是一个加了限制的线性表结构

  • 循环队列所占用的空间必须连续，循环队列的引入，目的是为了克服假溢出现象

  • 存放循环队列元素的数组data有10个元素，则data数组的下标范围是0~9

  • 在有n个元素的栈中，进栈操作的时间复杂度为O(1)，出栈操作的时间复杂度为O(1)n

  • 在顺序栈中，当栈顶指针为top=-1时表示栈空，top=MAXLEN-1时栈满；在链栈中，当栈顶指针等于NULL时表示栈空

  • 向栈中压入元素的操作是先移动栈顶指针，后存入元素

  • 从循环队列中删除一个元素时，其操作是先移动队首指针，后取出元素；在循环队列中，队首指针指向队首元素的前一个位置；在具有n个单元的循环队列中，队满时一共有n-1个元素

  • <1>数组Q[n]用来表示一个循环队列，f为当前队列头元素的前一位置，r为队尾元素的位置，假定队列中元素个数小于n，计算队列中元素的公式为(n+r-f)%n

  • <2>判定一个循环队列QU为满队列的条件是rear+1=front或者(QU->rear+1)%maxsize==QU->front

  • <3>判定一个循环队列为空的条件：rear=front

    1a03eafbf2c497134896133bacbda77

    e653c3162f8da4b8729779a3763431b

  • 如果一个栈A[n]为栈底，说明为向下生成堆栈，用A[T]表示栈顶元素，当推入一个新元素的时候，变量T减一,当弹出一个新元素的时候，变量T加一

  • 为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时，应将这两栈的栈底分别设在这片内存空间的两端，这样，只有当这两个栈的栈顶在到达栈空间的某一位置相遇时，才产生上溢。top[i]代表第i个(i=1,2)栈顶，栈满的条件是top[1]+1=top[2].

  • 带表头节点 的空循环双向链表的长度等于0

  • 用连接方式存储的队列，在进行删除运算时，头尾指针可能都要修改。(1.如果队列只有一个元素时，若这个元素出队，则队头队尾指针均要指向空，均要修改。2.如果队列有两个及以上元素时，则只需要修改队头指针不需要修改队尾指针)

  • 用单链表表示的链式队列的队头在链表的表头

5.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是

  • [ ] (rear+1)%n==front
  • [x] rear==front
  • [ ] rear+1==front
  • [ ] (rear-1)%n==front

6.如果以链表作为栈的存储结构，则出栈操作时

  • [ ] 必须判别栈是否满
  • [x] 必须判别栈是否为空
  • [ ] 必须判别栈元素类型
  • [ ] 队栈可以不做任何判别

7.在C语言中，一个顺序栈一旦被声明，其占用空间的大小

  • [x] 已固定 顺序栈的特点：顺序存储并空间固定
  • [ ] 不固定
  • [ ] 可以改变
  • [ ] 动态变化

8.已知先/后续遍历与中序遍历求后/先序遍历

  • 二叉树采用中序遍历可以得到接待你的有序序列
例子：设有一颗二叉树，其先序遍历是ABCDEFG，其中序遍历是CBAEDFG，则该二叉树的后续遍历为（CBEGFDA）
设有一颗二叉树，其后序遍历是DABEC，其中序遍历是DEBAC，则该二叉树的先续遍历为（CEDBA）

方法如下：1.先序遍历的第一个节点一定是根节点

​ 2.中序遍历的第一个节点一定是最左端的节点

​ 3.后续遍历是确定最后一个数为根节点（从下往上写）

例题1： (先序)

​ A A

​ B B

​ C C

​ D D

​ E E

​ F F

​ G G

​ C B A E D F G (中序)

注意：左子树的所有节点在父母节点左方，右子树的所有节点在父母节点右方(这就说明F为什么是D的右子树而不是E的右子树，因为如果F是E的右子树说明F也是D的左边但实际上不是)

例题2：（后序）

​ C C

​ E E

​ B B

​ A A

​ D D

​ D E B A C (中序)

已知二叉树求先根，中根，后根遍历

先根遍历：先再每个节点的左边画一个圈，然后用一根线从左上方出发，把圈连起来，先连到的先写

中根遍历：先再每个节点的下边画一个圈，然后用一根线从左上方出发，把圈连起来，先连到的先写

后根遍历：先再每个节点的右边画一个圈，然后用一根线从左上方出发，把圈连起来，先连到的先写

例子：如果是先根再左再根再右
注意：特点是凡是有左子树的节点，必间隔左子树的所有节点再出现(A B D)，反之就会马上重复出现(C E F G)

答案：ABCCEEBADFFDGG

1
2
3
4
			A
	B				D
C				F		G
  E

9.在下列存储形式中，哪一种不是数的存储形式

  • [ ] 双亲表示法
  • [ ] 孩子链表表示法
  • [ ] 孩子兄弟链表表示法
  • [x] 顺序存储表示法

10.在一棵度为3的树中（说明不是二叉树），度为3的节点数为2个，度为2的节点数为1个，度为1的节点数为2个，那么度为0的节点数为

  • [ ] 4
  • [ ] 5
  • [x] 6

  • [ ] 7

  • 树节点的度数是该节点字数或分支的个数，树的度数是其中节点度数的最大值

  • 边总数为3x2+2x1+1x2=10 (这个方法树和二叉树都适用)
    • 节点个数是（设度为0的节点个数是Q）2+1+2+Q
      • 由节点个数可以推出边的个数为2+1+2+Q-1（因为除了头节点上没有边，其它节点都有和父母节点相连的边）即：3x2+2x1+1x2=2+1+2+Q-1 则Q=6
如果该树为二叉树那么度为0的节点是度为2节点的个数加1

11.无向图的顶点个数为n，则该图最多有（）条边

  • [ ] n-1
  • [x] n(n-1)/2
  • [ ] n(n+1)/2
  • [ ] n^2
一个无向图顶点为n个，最多包含n(n-1)/2条边，最少包含n-1条边

12.要联通具有n个顶点的有向图至少需要（）条边

  • [ ] n-1
  • [x] n
  • [ ] n+1
  • [ ] 2n
n个节点的完全有向图含有边的数目为n*（n-1），完全有向图的定义是在有向图中，如果任意两给顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图

13.查找

  • 查找表是以集合为查找结构的

  • 顺序查找法适合于存储结构为顺序存储或是链式存储的线性表

  • 折半查找：以顺序方式存储（一个有序的单链表不能用折半查找的方式查找），且结点按关键字有序排列。折半查找方法：偶数查找第n/2个奇数查找第n/2 +1

    用折半查找表的元素的速度比用顺序法查找 不能确定,在有序的顺序储存表时，折半查找在大部分情况来说要快

    有一个顺序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}当折半查找值为82的节点时，要查找几次 4

    1. 先查找到45（13/2+1=7）
    2. 再查找到77
    3. 再查找到95
    4. 最后查找到82
    5. 分块查找：数据分成若干块，每块内数据不必有序（任意存放），但块间必须有序（按关键字有序），每块内最大（或最小）的数据组成索引块，首先查找索引表，再查找相应的块

  • 顺序查找，折半查找，分块查找都属于静态查找

  • 折半查找法的判定树和平均查找长度

    992cbaae8396f199c4a85f5f9591a05

    1c791b0ca508d43a6a631f9f8931d35

14.哈希表

在线性表的哈希存储中，装填因子ɑ又称装填系数，若用m表示哈希表的长度n表示线性线性表元素中的个数，则ɑ=n/m

构造哈希表的方法：

1.ASL成功：每个元素的查找次数/元素个数

2.ASL失败：后小于表长的最大素数个格子里的数不需要看他的失败次数，空格代表失败次数。所有(前最大素数给元素个空格中元素)失败次数/最大素数

注意：不成功的平均查找长度，算式的分母一直是题目哈希函数里mod后面那个数（题目给什么数据你就用什么）如果要自己写哈希函数那分母就是小于等于表长的最小素数（质数）——就是那个p

44bd411529b47903a4af66d6bd98b3d

ff4c675b0c0a4d266e8a5b655049393

62bc78f2f4e98ddaa58760c64ec0007

15.树和森林与二叉树的转换

  • 树转化为二叉树

    1. 给兄弟加线
    2. 给除长子外的孩子去线
    3. 层次调整

  • 森林转化成二叉树

    1. 将森林中的每棵树转化为二叉树
    2. 将所有的二叉树合并成一个树（将第二个二叉树的根节点作为第一棵二叉树根节点的右孩子，将第三棵二叉树的根节点作为第二个二叉树的右孩子）

  • 二叉树转化成树

    1. 如果一个节点的左孩子存在，则将左孩子的右孩子节点的右孩子节点都与该节点进行连线
    2. 去除右孩子的连线
    3. 层次调整

  • 二叉树转化成森林，看二叉树的根节点是否右右孩子，有就可以转化

    1. 先把根节点的右孩子去线，去掉后形成两个树，继续把根节点的右孩子去线
    2. 将分离的二叉树转化成树

IMG_20231213_230332

16.排序

插入排序—每次将一个待排序的记录按其关键字大小插入前面已经排好的子序列中（直接插入排序最坏所需时间O(n^2);平均所需时间O(n^2)）

注意：每个比较的元素是和前面排好序的最大的开始向前比较

希尔排序—每次分组为第一次分组大小的一半（奇数为n-1/2）（最坏所需时间O(n^2)）

CSDN_1702383846133

选择排序—有序区域初始为空，位于左端，无序区域位于右端，从无序区中选择关键字值最小的记录，将其与无序区第一个记录交换位置。直到全部待排序的数据元素排完 (直接选择排序最坏所需时间O(n^2)) 关键字比较次数与记录初始排列无关

CSDN_1702384800729

冒泡排序—将键值大的记录向序列的尾部移动，键值小的向序列头部移动 (最坏所需时间O(n^2)) 当元素从小到大排列，所需冒泡排序比较次数最少为n-1次，当元素从大到小排列，所需冒泡排序比较次数最多为(n-1)*n/2次

CSDN_1702384327083

归并排序（最坏所需时间O(nlog2n)）

  • 分解：将n个元素分成个含n/2个元素的子序列。
  • 解决：用合并排序法对两个子序列递归的排序。
  • 合并：合并两个已排序的子序列已得到排序结果。

快速排序

  • 随便找一个基准元素，将比这个基准元素小的放左边，大的放右边，相对顺序不变

    • 例如初始为50，20，10，40，70，80，90，60进行快速排序，以50为基准元素则第一次排序结果为20，10，40，50，70，80，90，60

  • 此时这个基准元素左右的元素，相当于被分成了两个子表，左表为20，10，40右表为70，80，90，60下一步就是分别在两个子表中各找一个基准元素，重复第一步（这时候不用管50的位置，50位置不变，相当于一个分界线）

    • 以20为左表的基准元素，则10要放在20左边，以70作为右表的基准元素则60要放在70左边。则第二次排序结果为10，20，40，50，60，70，80，90

  • 再把上一步的基准元素的左右两边（20的左边是10，右边是40；70的左边是60，右边是80，90）分成两个子表重复第二步

    • （因为20的左，右子表和70的左子表就只剩一个元素，所以不用再管）70的右子表为80，90，再以80为基准元素，以上就排列完成了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
例如：Q  H  C  Y  P  A  M  S  R  D  F X用快速排序
    以Q为基准元素拿出来:  ()  H  C  Y  P  A  M  S  R  D  F  X
        			  low							 high
        因为X大于Q：(为保证low，high中有一个为空，high向左移动)：()  H  C  Y  P  A  M  S  R  D  F  X
                                                         low						   high
        因为F小于Q，Q移到low：F  H  C  Y  P  A  M  S  R  D  ()  X
                          low						    high
        移动low：F  H  C  Y  P  A  M  S  R  D  ()  X
        	         low       			     high
        因为C小于Q，不动，继续移动low：F  H  C  Y  P  A  M  S  R  D  ()  X
        								   low					high
        因为Y大于Q，所以把Y移到high：F  H  C  ()  P  A  M  S  R  D  Y  X
        								  low				   high
        移动high：F  H  C  ()  P  A  M  S  R  D  Y  X
        				  low			    high
        因为D小于Q，把D移动到low：F  H  C  D  P  A  M  S  R  ()  Y  X
        							   low			     high
        移动low：F  H  C  D  P  A  M  S  R  ()  Y  X
        				   low		      high
        因为P小于Q不移动，移动low：F  H  C  D  P  A  M  S  R  ()  Y  X
        									 low	     high
        因为A小于Q不移动，移动low：F  H  C  D  P  A  M  S  R  ()  Y  X
        										low      high
        因为M小于Q不移动，移动low：F  H  C  D  P  A  M  S  R  ()  Y  X
        										   low   high
        因为S大于Q，移动S到high：F  H  C  D  P  A  M  ()  R  S  Y  X
        										  low    high
        移动high：F  H  C  D  P  A  M  ()  R  S  Y  X
        							 low high
        因为R大于Q不移动，移动high(此时high和low重合)：F  H  C  D  P  A  M  ()  R  S  Y  X
        											               	  high
        															  (low)
        把Q放入：F  H  C  D  P  A  M  Q  R  S  Y  X

堆排序

堆：二叉树，根节点的数值要比左右节点大
把一个二叉树变换为堆的方法：
  • 编号最大的非叶子节点是最大编号的叶子节点编号的一半，向下取整（n/2）。第一个调整的就是编号最大的非叶子节点
  • 接着调整其前面编号的其它节点，看是否满足大根堆（根节点要大于左右两字数，如不大于，选择最大的根节点与其交换位置）
  • 调整为大根堆后，将序号最大的叶子节点和根节点交换，这个时候最大编号的叶子节点存放的就是最大值的元素，之后就不用将它继续排序，直接拿出来作为顺序表末尾。再把剩下的n-1个元素继续大根堆排序。再反复重复这一步骤。

表中元素递增，分别用冒泡排序，堆排序，快速排序，归并排序—-冒泡排序最快，快速排序最慢

17.算法

  • 算法的特性：有穷性，确定性，可行性，输入，输出
  • 算法效率的度量可以分为时间复杂度和空间复杂度
  • 若一个算法中的语句频度之和为T(n)=7n+4n^2,则算法的时间复杂度为O(n^2)
  • 数据的四种存储结构是：顺序，链接，索引，散列

18.已知广义表，求表头表尾

表头：当广义表LS非空时，称第一个元素为LS的表头

表尾：称广义表LS中去除表头后其余元素组成的广义表为LS的表尾

表头是元素，表尾是广义表

广义表((a),((b),(c,d,e)))的表头和表尾分别是(a),((b),(c,d,e))
广义表(a,b,c)的表头和表尾分别是a,(b,c)
广义表(a,(b))的表头和表尾分别是a，((b))
广义表(a)的表头和表尾分别是a,()
  • 广义表可以递归

广义表的长度和深度：

对于广义表L=((a,b,c)); L顶层就一个元素那就是(a,b,c)这个广义表，因此L的长度为1，对于深度，外面L是第一层，内部的(a,b,c)是第二层，而a，b，c都是原子元素，所以没有更深的层，因此深度为2

19.二叉树

  • 对于一个二叉树来说，第i层最多有2^(i-1)个节点
  • 由3个节点构成的二叉树共有5个不同的结构

20.已知广义表画出树

每一层是上一层的孩子节点，每一层逗号左边是上一层的左节点，逗号右边是上一层的右节点（根（左 ，右））

例如：(A ( B ( C , D ( E ) ) ) )

  • A的左节点是B 因为B同层没有逗号，所以A没有右节点
  • C是B的左节点D是C的右节点
  • E是D的左节点

21.哈夫曼树的构造和带权路径的求法

例如：W（权值集合）=（5，29，7，8，14，23，3，11）构造哈夫曼树

  • 把权值从小到大排序：3，5，7，8，11，14，23，29
  • 找最小的两个权值：3，5
  • 再把最小两个权值的和（8）放到权值集合当中，把已经找出的两个最小权值删除：8，7，8，11，14，23，29
  • 构成新的权值集合后再重复第一步去排序：7，8，8，11，14，23，29
    • 把7，8删掉，求和为15，把15放入：15，8，11，14，23，29
    • 排序：8，11，14，15，23，29
    • …………
注意：重要的是层次排列，每个放入哈夫曼树的值要找到其对应的求和

带权路径长度的求和（左0右1）

把每个节点的左右分支标成0和1，哈夫曼编码就是从头到这个节点所经过路径用0，1代替。如图，7的哈夫曼编码是1110

wpl（带权路径长度）：带权叶子节点×它的路径长度，再把每个相加起来。例如上图：3×4+5×4+11×3+23×2+29×2+14×3+7×4+8×4

  • 首先，哈夫曼树是一个二叉树，并且哈夫曼树的度只有两种情况，一个是只有两个度的节点，一个树没有度的节点。例如：如果一个哈夫曼树一共有11个节点，则叶子节点有（6）个（哈夫曼树的节点有m个，则叶子节点有(m+1)/2个，分支节点有(m-1)/2个）

22.强连通分量的个数（有向图中的定义）

强连通分量—-有向图中极大联通子图
  • 找环（圈）
  • 将整个环变成一个点
  • 简化成新图后就方便找到强连通分量（有去有回）注意：一个点也算一个强连通分量：图中v1，v5，v6就分别算一个强连通分量，加上可以被看做连通分量的环，一共四个强连通分量

26208517024498982_edit_208218952811641

连通分量是无向图中的定义，连通分量指的是不互相连通的连通图的个数
  • 完全图：也称简单完全图。一个图任意两个顶点之间都有边的话，该图就称为完全图。

23.图，树，邻接矩阵，邻接表的深度遍历/广度遍历 最小生成树的算法

深度遍历：走路径，走过的不再走
广度遍历：先遍历离根节点相距离为1的节点，再遍历距离与这些节点相距为1的节点…………
邻接树，图，矩阵的深度广度优先遍历很简单，这里不多讲（临界矩阵的遍历，先画出图，再遍历）

邻接表每一个链表后的节点相当于一层，反应出度情况

深度优先遍历：v1 v2 v4 v3 v5 v6

广度优先遍历：v1 v2 v3 v4 v5 v6

逆邻接表：反应顶点的入度情况

24.生成树

连通图生成树 （防止环路生成信息风暴），非连通树生成森林 N个顶点的连通图的生成树含有N-1个边
注意：生成树是对应连通图来说，生成树就是极小连通子图，包含n个顶点，只有足以构成一棵树的n-1条边，而生成森林是对应非连通图来说
一个无向连接图可能有多棵形态不同的树，在一个赋权无向连通图的所有生成树中，生成树各边上权值的总和最小的生成树称为最小生成树

最小生成树

  • 路径加起来权值是最小的
  • 路径不能构成环路
    • Prime算法是选项点，每次将最小权值的顶点连入成树。每次加入的点都看成一个整体，看连接这个整体的最小路径是和哪个节点连接，找到这个节点，再把这个节点和之前的整体构成一个新的整体。
    • Kruskal算法首先把节点画出来，先不要连接，然后依次找路径最小的节点，注意判断是否构成环路

25.平衡二叉树

  • 插入节点(记住要看顺序)

    • 先把插入的那个节点插入到应该插入的位置（按二叉排序树的特点插入）

    • 从下往上找第一个的不平衡节点（编号最小的不平衡节点）（这个节点左右子树层数相减-1），把这个节点以及它不平衡（最长长度）的左子树或者右子树中拿出来包含这个不平衡节点的3个节点（进行平衡二叉树方式）调整，剩下子树的节点还是根据二叉排序树的特点（按每层从左到右）放入到这三个调整完的节点上去。

  • 一个表（数的集合）构造成平衡二叉树则相当于把每个节点插入到的树中，若插入某个节点时树不平衡则用上述方法

二叉排序树—左边小右边大

平均查找长度ASL=（1×第一行元素个数+2×第二行元素个数+3×第三行元素个数+……）/元素总个数

折半查找的判定树—先把元素按升序排列，以中间数据为根节点，根节点左边是它的左子树，右边是他的右子树

26.稀疏矩阵的两种表示方法

  1. 三元组表

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    //已知一个6×5的稀疏矩阵如下所示，写出它的三元组线性表
    | 0  0  0  0  1	|
    | 0  0  0  0  0	|
    | 0 -1  0  0  0	|
    | 0  0  0  0 -2	|
    | 5  0  0  0  0	|
    | 0  0  7  0  0	|
    (i,j,e)//i为行数，j为列数，e为元素，0行0列开始，转置前，行从0到5
     0 4 1				       0 |0 4 5
     2 1 -1   转置后(列从0到5)   1 |1 2 -1
     3 4 -2   -------------->  2 |2 5 7
     4 0 5					   3 |4 0 1
     5 2 7					   4 |4 3 -2 (j,i,e)
     //计算数组num和k的元素，col和num表示第几列有几个非零元素（看转置后的表），k[i]指的是每个列的第一个元素的标号值
    col   0  1  2  4
    num   1  1  1  2
    k[i]  0  1  2  3

  1. 十字链表法

27.设目标串“abccdcdccbaa”，模式串“adcc”第几次匹配成功

  • [ ] 5
  • [x] 6
  • [ ] 7

28.在单链表p所指节点之前插入一个s所指节点

1
2
3
4
5
6
//因为是单链表，所以找不到p节点的上一个节点，所以只能让s节点插入到p节点之后，然后s节点数据和p节点数据交换，从而达到前插的目的
s->next=p->next;
p->next=s;
temp=p->data;
p->data=s->data;//相当于把p节点滞空
s->data=temp;

29.栈的阅读题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void main( )
{
    Stack S;
    Char x,y;
    InitStack(S);
    x=’c’;y=’k’; //x=‘c’, y=‘k’
    Push(S,x); //x=‘c’,y=‘k’,S=“c”
    Push(S,’a’); //x=‘c’,y=‘k’,S=“ac”
    Push(S,y); //x=‘c’, y=‘k’, S=“kac”
    Pop(S,x); //x=‘k’,y=‘k’,S=“ac”
    Push(S,’t’); //x=‘k’,y=‘k’,S=“tac”
    Push(S,x); //x=‘k’,y=‘k’,S=“ktac”
    Pop(S,x); //x=‘k’,y=‘k’ S=“tac”
    Push(S,’s’); //x=‘k’,y=‘k’ S=“stac”
    while(!StackEmpty(S))\
    {
       Pop(S,y); //依次为y=‘s’,y=‘t’,y=‘a’,y=‘c’
       printf(y); //打印依次为s,t,a,c\n}\nPrintf(x);//x=‘k’\n
    }
}

30.串，数组，广义表

  • 串是一种特殊的线性表，其特殊性体现在数据元素是一个字符

31.设串s1=’ABCDEFG’,s2=’PQRST’,函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,len(s2)),sub(s1,len(s2),2)）的结果串是：

  • [ ] BCDEF
  • [ ] BCDEFG
  • [ ] BCPQRST
  • [x] BCDEFEF

32.若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是

  • [ ] 1234
  • [ ] 4321
  • [x] 4231

  • [ ] 4213

  • 输入受限的双端队列是两端都可以删除，只有一端可以插入的队列

  • 输出受限的双端队列是两端都可以插入，只有一端可以删除的队列

33.按行列存储

  • 一般情况当行与列的上下界都相同时，按行存储的A[ I , J ]，与按列存储的A[ J , I ]地址相等

34.编写算法，删除顺序表前面的8个元素。如果顺序表中的元素少于8个则删完为止

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int delete(sequentlist *s)
{
    int i;
    if(s->data<=8)
    {
        s->last=0;
        return 0;
    }
    for(i=0;i<s->last-8;i++)
    {
        s->data[i]=s->data[i+8];
    }
    s->last-=8;
    return 0;
}

35.编写算法，输出一棵二叉树的第i层的所有节点的值，假设根节点是第1层

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typefef struct linkNode
{
    int data;
    struct linkNode *lchild *rchild;
}Node;
void outi(Node *tree,int i)
{
    if(tree==NULL)
        return;
    if(i==1)
    {
        printf("%d\n",tree->data)
        return;
    }
    outi(tree->lchild,i-1);
    outi(tree->rchild,i-1);
}

36.编写算法，判断单链表的元素值是不是递增的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int isviset(L)
linklist *L;
{
    linklist *p;
    p=L;
    while(p->next!=NULL)
    {
        if(p->data<p->next->data)
            p=p->next;
        else
            return 0;
    }
    return 1;
}

37.