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

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