1．我们知道计算机只能执行机器指令，为什么它能运行用汇编语言和高级语言编写的程序？
答：靠汇编程序将汇编语言或高级语言翻译转换为目标程序（即机器语言）。
2.【严题集1.2②】数据结构和数据类型两个概念之间有区别吗？
答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。
3. 简述线性结构与非线性结构的不同点。
答：线性结构反映结点间的逻辑关系是 一对一的，非线性结构反映结点间的逻辑关系是多对多的。
1.试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？
答：① 顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。
优点：存储密度大（＝1？），存储空间利用率高。缺点：插入或删除元素时不方便。
②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（<1），存储空间利用率低。
顺序表适宜于做查这样的静态操作；链表宜于做插入、删除这样的动态操作。
若线性表的长度变化不大，且其主要操作是查，则采用顺序表；
若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。
2 .描述以下三个概念的区别：头指针、头结点、首元结点（第一个元素结点）。在单链表中设置头结点的作用是什么？
答：首元结点是指链表中存储线性表中第一个数据元素a1的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一
处理。头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空。否则表示空表的链表的头指针为空。这三个概念对单链表、双向链表和循环链表均适用。是否设置头结点，是不同的存储结构表示同一逻辑结构的问题。
    头结点
head
data
link
            头指针              首元结点
简而言之，
头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；
头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息（内放头指针？那还得另配一个头指针）
首元素结点是指链表中存储线性表中第一个数据元素a1的结点。
、线性表具有两种存储方式，即顺序方式和链接方式。现有一个具有五个元素的线性表L={23，17，47，05，31}，若它以链接方式存储在下列100～119号地址空间中，每个结点由数据（占2个字节）和指针（占2个字节）组成，如下所示：
05
U
17
X
23
V
31
Y
47
Z
^
^
100
120
其中指针X，Y，Z的值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地址为多少？（10分）
答：X=  116    Y=  0    Z=  100  首址=  108    末址=  112   
1.说明线性表、栈与队的异同点。
答：相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。
不同点：①运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。
② 用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理、指令寄存及其他运算等等。
2.设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。
答：至少有14种。
① 全进之后再出情况，只有1种：4，3，2，1
② 进3个之后再出的情况，有3种，3,4,2,1  3,2,4,1  3,2,1,4
③ 进2个之后再出的情况，有5种，2,4,3,1  2,3,4,1  2,1, 3,4  2,1,4,3  2,1,3,4
④ 进1个之后再出的情况，有5种，1,4,3,2  1,3,2,4  1,3,4,2  1, 2,3,4  1,2,4,3
3.假设正读和反读都相同的字符序列为“回文”，例如，‘二叉树公式abba’和‘abcba’是回文，‘abcde’ 和‘ababab’则不是回文。假设一字符序列已存入计算机，请分析用线性表、堆栈和队列等方式正确输出其回文的可能性？
答：线性表是随机存储，可以实现，靠循环变量（j--）从表尾开始打印输出；
堆栈是后进先出，也可以实现，靠正序入栈、逆序出栈即可；
队列是先进先出，不易实现。
哪种方式最好，要具体情况具体分析。若正文在机内已是顺序存储，则直接用线性表从后往前读取即可，或将堆栈栈顶开到数组末尾，然后直接用POP动作实现。（但堆栈是先减后压还是……）
若正文是单链表形式存储，则等同于队列，需开辅助空间，可以从链首开始入栈，全部压入后再依次输出。
4.顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？
答：一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。
采用循环队列是解决假溢出的途径。
另外，解决队满队空的办法有三：
1设置一个布尔变量以区别队满还是队空；
2浪费一个元素的空间，用于区别队满还是队空。
3使用一个计数器记录队列中元素个数（即队列长度）。
我们常采用法②，即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素。
判断循环队列队空标志是： f=rear      队满标志是：f=(r+1)%N
5.设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有
① front=11，rear=19;    ② front=19，rear=11；问在这两种情况下，循环队列中各有元素多少
个？
答：用队列长度计算公式：  (N＋r－f)% N
① L=（40＋19－11）% 40=8              ② L=（40＋11－19）% 40=32
1.一棵度为2的树与一棵二叉树有何区别？
答：度为2的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序的。即，在一般树中若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即使是一个孩子也有左右之分。
C的结点类型定义如下：
struct node
{char data;
struct node *lchild, rchild;
};
C算法如下：
void traversal(struct node *root)
{if (root)
{printf(“%c”, root->data);
  traversal(root->lchild);
  printf(“%c”, root->data);
traversal(root->rchild);
}
}
2.设如下图所示的二叉树B的存储结构为二叉链表，root为根指针，结点结构为：（lchild,data,rchild）。其中lchild，rchild分别为指向左右孩子的指针，data为字符型，root为根指针，试回答下列问题：
1.对下列二叉树B，执行下列算法traversal(root)，试指出其输出结果；
2.假定二叉树B共有n个结点，试分析算法traversal(root)的时间复杂度。（共8分）
二叉树B
解：这是“先根再左再根再右”，比前序遍历多打印各结点一次，输出结果为：A B C C E E B A D F F D G G
特点：①每个结点肯定都会被打印两次；②但出现的顺序不同，其规律是：凡是有左子树的结点，必间隔左子树的全部结点后再重复出现；如A，B，D等结点。反之马上就会重复出现。如C，E，F，G等结点。
时间复杂度以访问结点的次数为主，精确值为2*n，时间渐近度为O(n).
3.给定二叉树的两种遍历序列，分别是：
前序遍历序列：D，A，C，E，B，H，F，G，I；  中序遍历序列：D，C，B，E，H，A，G，I，F，
试画出二叉树B，并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思想方法。
解：方法是：由前序先确定root，由中序可确定root的左、右子树。然后由其左子树的元素集合和右子树的集合对应前序遍历序列中的元素集合，可继续确定root的左右孩子。将他们分别作为新的root，不断递归，则所有元素都将被唯一确定，问题得解。
        D
        A
        C                  F
E          G
B      H          I
4.给定如图所示二叉树T，请画出与其对应的中序线索二叉树。
解：要遵循中序遍历的轨迹来画出每个前驱和后继。
中序遍历序列：55  40  25  60  28  08  33  54
                        28
2533
        40      60    08        54
 
55
五、阅读分析题（）
1.试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。
答：DLR：A B D F J G K C E H I L M
    LDR: B F J D G K A C H E L I M
    LRD：J F K G D B H L M I E C A
2. （P60 4-27）把如图所示的树转化成二叉树。

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