数据结构实验考试题.doc

数据结构实验考试题
1. 已知线性表A,B,C是递增有序的线性表。要求对A表作如下运算：删去那些既在B表中出现又在C表中出现的元素。A,B,C以顺序表存储。
2. 假设有两个按元素值递增有序排列的线性表A和B,均以单链表作存储结构。请编写程序将A表和B表归并成一个按元素递减有序排列的线性表C,并要求利用原表结点空间存放C表。
3. 求以递增序排列的两个线性表A和B的交集，将结果存于新表C中。要求C中元素仍然以递增序排列，并且C中没有重复的元素。以顺序结构实现此算法。
4. 设A=(a1, ... ,am)和B=(b1,...,bn)均为有序线性表，A' 和 B' 分别为A、B中除去最大共同前缀后的子表。若A' = B' = 空，则A=B；若A' = 空表，B'≠空表，或者两者均不空且A'首元小于B'首元，则A<B；否则A>B。
5. 单链表中的元素以递增序存放,写一算法,删除表中所有值大于mink且小于maxk的元素(如果这样的元素存在).
6. 假设以循环链表作稀疏多项式的存储结构，编写求两个稀疏多项式乘积的算法。要求：不破坏原来的多项式链表。
7. 设两个栈共享向量空间v(1:m),它们的栈底分别在向量的两端，进栈的每个元素只占用一个分量。写出这两个栈公用的栈操作算法：push(i,x), pop(i)和top(i,x)。其中i=0或1，分别代表两个不同的栈。
8. Ackerman函数的非递归解法
akm(m,n) = n + 1 (当m = 0时)
akm(m-1,1) (当m <> 0 且 n = 0时)
akm(m-1,akm(m,n-1)) (当m<>0 且 n<>0时)
9. 求一个广义表的深度*广义表的深度即是括号的最大层数。通过记录一个表中所出现的配对括号的层数，就可以求出广义表的深度。
10. 具有头结点的两个单链表的链接。已知：头结点的数据段中放的是链表长度。两个链表的链接是指将一个链表的第一个元素链接到另一个链表的尾部。要求：算法必须有最小的时间代价
l 以数组储存的队列，设置rear和quelen两个变量分别表示队尾元素位置和队列长度。写出入/出队列的算法。
l 以数组存储的循环队列，编写能充分利用数组中每个元素的入/出队列算法。此题需要设立一个标志，以指示当rear = front时队列是空还是满。
l 求矩阵中所有的马鞍点。若矩阵 A[0:m-1,0:n-1]中的某个元素A[i,j]是第i行中的最小值，同时右又是第j列中的最大值，则它就是马鞍点。
l 用堆栈实现判断一个算术表达式中括号是否配对的算法。假设一个算术表达式中可以包括(),[],{}三类括号，且这三种括号可以任意嵌套使用。
l 试编写一个将百分制转换成五分制的算法，要求其时间性能尽可能地高。假定学生成绩的分布情况如下：
分数 0-59 60-69 70-79 80-89 90-100
比例 0.05 0.15 0.40 0.30 0.10
l 设线性表存于数组array中，且递增有序。将一个新元素x插入到线性表中，并保持排序状态。
l 假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针，编写在链表中删除s所指结点的前驱结点的算法。
l 试以循环链表作稀疏多项式的存储结构，编写求其导函数的算法。要求利用原结点空间并释放多余结点。
l 已知单链表表示的线性表中含有三类字符数据元素，一类为数字，一类为字母，一类为其他符号。试编写算法构造三个以循环链表表示的线性表，使每个表中只含有同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。
l 试设计一个算法，将数组A(0:n-1)中的元素循环右移k位，并要求只用一个元素大小的附加存储，元素移动或交换的次数为O(n)。
l 用一维数组做存储结构，就地逆置一线性表。如：(a1,a2,...an)逆置后为(an,an-1,...,a1)
l 设有一个双链表，每个结点中除了有pre,data和next三个域外，还有一个访问 频度域freq，在链表起用之前，所有的freq = 0。每当在链表进行一次LOCATE(l,x) 运算时，令元素值等于x的结点中freq域的值增1，并使此链表中结点保持按访问频度递减的顺序排列，以便使频繁访问的结点总是靠近表头。
l 背包问题：假设一个背包可以装入总重量为T的物品，现在有n件物品，其重量分别为： w1,w2,...,wn。求{wx1,wx2,...,wxn}包含于{w1,w2,...,wn}使得wx1+wx2 + ... + wxn = T。（wi <> wj, i<>j; wxi <> wxj, i <>j）
l （1）若n=1,则当w1 = T时有解；（2）若n>1,则此题化为：求T' = T - wj, 物品重量为w1,w2,... w(j-1),w(j+1),...,wn时的背包问题。j = 1,2,...,n 如此递归，可解。
l 写出求递归函数f(n)的非递归算法：
f(n) = n+1 (当n=0)
f(n) =n*f((int)(n/2)) (当n>0)
l 假定用两个一维数组L(0:n-1)和R(0:n-1)作为有n个结点的二叉树的存储结构，L[i]和R[i]分别指示结点i的左孩子和右孩子，-1 表示空。
（1）判别结点u是否为结点v的子孙；
（2）先由L和R建立一维数组T(0:n-1),使T中第i个元素(i=0,2,...,n-1)
指示结点i的双亲，然后写判别结点u是否是v的子孙的算法。
l 通过键盘输入的扩充二叉树的前序遍历序列, 建立二叉树，然后按中序和后序输出此树，并求该树的叶结点个数和度数为2的结点个数。假设二叉树结点的数据为char型，其中扩充结点用'*'号表示。
l 在一棵以二叉链表存储的二叉树中，求在前序序列中排在第k位的结点假设表达式由单字母变量和双目运算符构成，写一个算法，判断表达式是否为正确的后缀表达式。如果是，将其转化为前缀表达式。
l 假设二叉树中左分支的标号为"0",右分支的标号为"1"，并对二叉树增设一个头结点，令根结点为其右孩子。则：从头结点到树中任意一结点所经分支的序列为一个二进制序列，将这个二进制序列的值作为该结点对应的值。
l 已知一棵非空二叉树以顺序结构存储，变量i为树中某结点在顺序存储结构中的下标值，写一个尽可能简单的算法，求出于该结点对应的值。如：
(a)
0/ \1
(b) (c)
0/ \1
(e) (g)
0/
(h) h对应的二进制序列为1110,即十进制的14。
l 假设二叉树T中至多有一个结点的数据域为x,编写算法拆去以该结点为根的子树，使原树分为两棵。例如x = 9,二叉树的变化如下：
13
/\
3 16
/ \ \
2 9 27
/ / \
4 6 11
拆开后：
13
/\
3 16
/ \
2 27
/
4

9
/ \
6 11
l 用递归的方法复制一棵二叉树，假设二叉树以二叉链表存储。
l 设计一个算法输出已知二叉树中所有叶子结点的值
l 已知一棵二叉树以二叉链表为存储结构，编写如下算法：对于树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。
l 编写算法查找二叉树中数据域值为X的结点（假定各结点的数据域值各不相同），并打印出X所有祖先的数据域值。
l 编写判断两个二叉树是否相等的算法。若T1与T2是等价的，则要么T1与T2是空树，要么T1和T2的值相同并且T1、T2的左右子树分别相等。
l 编写判断两个二叉树是否相似的算法。若T1与T2是相似的，则要么T1与T2是空树，要么T1和T2都不是空树并且T1、T2的左右子树分别相似。假设树是以二叉链表形式存储的。
l 写一算法,判断一棵二叉树是否是完全二叉树。
l 对二叉树进行层次遍历
l 求一棵二叉树中每个层次的结点数
l 编写一个算法，输出以二叉树表示的算术表达式。要求：在需要加括号的地方加上括号。
l 假设以二叉链表存储的二叉树中，每个结点所含的数据元素均为单字母，编写算法，按树状打印二叉树。如：
a
/ \
b c
\ /
d e
\
f 打印为：
c f e a d b
l 一棵n个结点的完全二叉树存放在二叉树的顺序存储结构中。编写非递归算法对该树进行前序遍历。
l 以二叉链表为二叉树的存储结构，写出求某个结点的父结点的算法。
l 编写算法交换二叉树中所有结点的左、右子树。
l 一棵二叉树的前序序列和中序序列分别存在两个数组中，编写算法，建立以二叉链表为结点的该二叉树。
l 一棵二叉树的后序序列和中序序列分别存在两个数组中，编写算法，建立以二叉链表为结点的该二叉树。
l huffman算法
l 图解最小生成树算法
l 无向图邻接表生成算法
l 从一个顶点到其它顶点的最短路径算法
l 图的各个顶点最短路径
l 图的深度遍历
l 图的广度遍历
l 顺序查找算法
l 二分查找算法
l 冒泡排序算法
l 快速排序算法
l 希尔排序算法
l 直接插入排序
l 基数、归并排序算法