简述栈和线性表的差别。

问答题简述栈和线性表的差别。

参考答案： 线性表是具有相同特性的数据元素的一个有限序列。栈是限定仅在表尾进行插入或删除操作的线性表。

您可能感兴趣的试卷

你可能感兴趣的试题

1.问答题 稀疏多项式采用的循环链表存储结构LinkedPoly定义为：

试编写算法，将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间构成这两个链表。

参考答案：

2.问答题 稀疏多项式采用的循环链表存储结构LinkedPoly定义为：

试以循环链表作稀疏多项式的存储结构，编写求其导函数的方法，要求利用原多项式中的结点空间存放其导函数多项式，同时释放所有无用结点。

参考答案：

3.问答题 稀疏多项式采用的顺序存储结构SqPoly定义为：

采用上题给定的条件和存储结构，编写求P（x）=P_n1（x）-P_n2（x）的算法，将结果多项式存放在新辟的空间中，并分析你的算法的时间复杂度。

参考答案：

4.问答题 稀疏多项式采用的顺序存储结构SqPoly定义为：

已知稀疏多项式P_n（x）=c₁x^e1+c₂x^e2+…+c_mx^em，其中n=e_m＞e_m-1＞…＞e₁≥0，c_i≠0（i=1，2，…，m）。m≥1试采用存储量同多项式项数m成正比的顺序存储结构，编写求P_n（x₀）的算法（x₀为给定值），并分析你的算法的时间复杂度。

参考答案：

5.问答题设有一个双向循环链表，每个结点中除有pre，data和next三个域外，还增设了一个访问频度域freq。在链表被起用之前，频度域freq的值均初始化为零，而每当对链表进行一次Locate（L，x）的操作后，被访问的结点（即元素值等于x的结点）中的频度域freq的值便增1，同时调整链表中结点之间的次序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合上述要求的Locate操作的算法。

参考答案：

6.问答题设以带头结点的双向循环链表表示的线性表L=（a₁，a₂，…，a_n）。试写一时间复杂度O（n）的算法，将L改造为L=（a₁，a₃，…，a_n，…，a₄，a₂）。

参考答案：

7.问答题假设在算法描述语言中引入指针的二元运算“异或”，若a和b为指针，则a⊕b的运算结果仍为原指针类型，且a⊕（a⊕b）=（a⊕a）⊕b=b；（a⊕b）⊕b=a⊕（b⊕b）=a。则可利用一个指针域来实现双向链表L。链表L中的每个结点只含两个域：data域和LRPtr域，其中LRPtr域存放该结点的左邻与右邻结点指针（不存在时为NULL）的异或。若设指针L.Left指向链表中的最左结点，L.Right指向链表中的最右结点，则可实现从左向右或从右向左遍历此双向链表的操作。试写一算法按任一方向依次输出链表中各元素的值。

参考答案：

8.问答题已知由一个线性链表表示的线性表中含有三类字符的数据元素（如：字母字符、数字字符和其他字符），试编写算法将该线性表分割为三个循环链表，其中每个循环链表表示的线性表中均只含一类字符。

参考答案：

9.问答题已知有一个单向循环链表，其每个结点中含三个域：pre，data和next，其中data为数据域，next为指向后继结点的指针域，pre也为指针域，但它的值为空，试编写算法将此单向循环链表改为双向循环链表，即使pre成为指向前驱结点的指针域。

参考答案：

10.问答题假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。

参考答案：