1．简述算法的概念及其五个重要特性。
2．下图是用邻接表存储的图，请画出此图，写出其邻接矩阵以及从c点开始分别按广度优先搜索和深度优先搜索遍历该图的结果。
给定一棵用二叉链表表示的二叉树，其根指针为root，编写求此二叉树叶结点个数的算法，要求先写出二叉链表的类型定义。
2.编写简单选择排序的算法。
1．用链表表示线性表的优点是（ ）
a. 便于随机存取 b. 花费的存储空间比顺序存储少。
c. 便于插入和删除 d. 数据元素的物理顺序和逻辑顺序相同。
2． **性表中采用折半查找法查找元素，该线性表应该（ ）
a．元素按值有序b．采用顺序存储。
c．元素按值有序，且采用顺序存储 d．元素按值有序，且采用链式存储。
3．以二叉链表作为二叉树的存储结构，在具有n个结点的二叉链表中（n>0）空链域的个数为（ ）
a. 2n-1 b. n-1 d.2n+1
4．设循环队列中数组的下标范围是1～n，其头尾指针分别为f和r，则队列中元素的个数为（ ）
a. r-f b. r-f+1 c. (r-f+1) mod n d. (r-f+n) mod n
5.在一个单链表中，已知q所指结点是p的前趋结点，要在p的前面插入s结点，则执行（ ）
a. s->next=p->next；p->next=s；
b. p->next= s->next； s->next=p；
c. q->next=s；s->next=p； d. p->next=s；s->next=q；
6．具有n条边的无向图的邻接表的存储中，边结点的个数为（ ）
a. n b. 2*n c. n/2 d. n*n
7．在有n个叶结点的哈夫曼树中，其结点总数为（ ）
a. 不确定 b. 2n c.2n+1 d. 2n-1
8．表长为25的哈希表，按照除留余数法即hash(key)=key mod p，建立哈希函数，则p应取（ ）
a. 26 b.25 c.15 d.23
9．图的深度优先搜索可以看成是树的（ ）遍历的推广。
a. 先序 b.中序 c. 后序 d.层次。
10．初始数据有序时，（ 排序方法会出现“蜕化”现象。
a. 归并 b.起泡 c.快速 d.堆。
11．一个栈的输入序列是a、b、c、d，则不可能的输出序列是( )
a．a、b、c、d b．d、c、b、a c．a、c、d、b d．d、a、b、c
12．任何一个无向连通图的最小生成树( )
a．一定只有一棵 b．有一棵或多棵。
c．一定有多棵 d．可能不存在。
13．如果一棵二叉树先序遍历序列和其后序遍历序列正好相反，则该二叉树一定是（ ）
a．空或只有一个结点b．高度等于其结点数。
c．任一结点均无左子树 d．任一结点均无左子树。
14．对200个元素利用折半查找法进行查找时，其最大比较次数为（ ）
a. 11 b. 10 c. 9 d. 8
15．一组记录的关键字为(46,79,56,38,40,84)，利用快速排序的方法，以第一个记录为枢轴得到的一次划分结果为（ ）
a．38，40，46，56，79，84 b．40，38，46，79，56，84
c．40，38，46，56，79，84 d．40，38，46，84，56，79
16．在有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。
a. 1/2 b. 1 c. 2 d. 4
17．一棵完全二叉树共有700个结点，其叶结点个数为（ ）
a. 349 b. 350 c. 351 d. 以上都不正确。
18．关键路径是aov网中（ ）
a．从源点到汇点的最短路径 b．从源点到汇点的最长路径。
c．最长的回路且按拓扑排序 d．最短的回路。
19．对二叉排序树进行（ ）遍历，可得结点数据的有序序列。
a. 先序 b. 中序 c. 后序 d. 层次。
20．根据二叉树的定义，含有3个结点的二叉树共有（ ）不同的形态。（不考虑结点内容）
a. 3b. 4c. 5 d. 6
数据结构与算法
本章知识要点 算法的基本概念 数据结构的定义 线性表的定义和存储 树 二叉树的定义和存储 查找与排序算法。算法 algorithm 是一组有穷的规则，规定了解决某一特定类型问题的一系列运算，是对解题方 与完整的描述。算法是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中...
算法与数据结构
学院专业姓名学号。实验1 线性表的操作 12学时 问题描述 假设一个班级内有n个学生，定义一个学生类和一个班级类。学生类中包括学号 姓名 性别 年龄 专业等属性 班级类包括一个学生对象链表。定义如下 class student class myclass student stu head 链表表头指...
算法与数据结构
数据结构与算法课程设计。题目 集合运算问题 排序算法比较问题 跳马问题 构造可以使n个城市连接的最小生成树 目录。摘要 4 一 集合运算问题 5 1.采用类语言定义相关的数据类型 5 2.算法设计 5 3.函数的调用关系图 6 4.调试分析 6 5.测试结果 7 6.源程序 带注释 7 二 算法排序...