一、单选题（每题2分，共30分）
1．以下数据结构中，（）是非线性数据结构。
A.树
B.字符串
C.队
D.栈
2．下面算法的时间复杂度为（）
int f(int n)
if (n==0 || n==1)
return 1;
else return n * f(n-1);
A.O(1)
B.O(n)
C.O(n的平方)
D.O(n!)
3．下述哪一条是Array这种数据结构的优点？（）
A.存储密度大
B.插入运算方便
C.删除运算方便
D.可方便地用于各种逻辑结构的存储表示
4．下面关于字符串的叙述中，哪一个是不正确的？（）
A.串是字符的有限序列
B.空串是由空格构成的串
C.模式匹配是字符串的一种重要运算
D.串既可以采用顺序存储，也可采用链式存储5．在无序数组中，允许重复会导致（）。
A.所有操作时间都会增加
B.总会增加插入时间
C.在某些情况下查找时间的增加
D.有时会减少插入时间
6．若某数据结构最常用的操作是存取任一指定序号的元素和在尾部进行插入和删除运算，则利用（）存储方式最节省时间。
A.Array
B.双链表
C.带头结点的双循环链表
D.单循环链表
7．非空的循环单链表的尾结点p满足（）。
A.p.next==first
B.p.next == null
C.p == null
D.p == first
8．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）
A.p.next = s; s.next = p.next;
B.s.next = p.next;p.next = s;
C.p.next = s; p.next = s.next;
D.p.next = s.next; p.next = s;
9．有六个元素6,5,4,3,2,1.顺序进栈。问下列哪一个不是合法的出栈序列？（）
A.5 4 3 6 1 2
B.4 5 3 1 2 6
C.3 4 6 5 2 1
D.2 3 4 1 5 6
10．在Hanoi塔问题中，若A塔上有3片圆盘。都要搬到C塔上去。则下列语句（）是错误的。
11．归并排序的主要缺点是（）。
A.没有递归
B.使用更多的存储空间
C.尽管比插入算法快，但是它比快速排序慢得多
D.需要7次才能完成工作
12．树最适合用来表示（）
A.有序数据元素
B.无序数据元素
C.元素之间具有分支层次关系的数据
D.元素之间无联系的数据
13．引入二叉树的主要目的是（）
A.加快查找结点的前驱或后继的速度
B.能较快地进行插入与删除
C.为了能方便的找到双亲
D.使遍历的结果唯一
14．要连通具有N个顶点的有向图，至少需要（）条边。
A.n-1
B.n
C.n+1
D.2n
15．下列排序算法中，在待排序数据已有序时，花费时间最少的是（）排序。
A.插入
B.冒泡
C.快速
D.选择
二、填空题（每题2分，共20分）
1.在一个长度为n的顺序表中第i个元素（1<= i <=n）之前插入一个元素时，需向后移动---
元素。
2.对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为
---，在给定值为x的结点后插入一个新结点的时间复杂度为---。
3.顺序存储结构是通过————表示元素之间的关系的;链式存储结构是通过——表示元
素之间的关系的。
4.栈是操作——的数据结构，其运算遵循——的原则。
5.向空队列中插入15，25，35和45.然后移除三个数据项，队列中剩下的数据项是——。
6.如果用户在如下函数：
int triangle(int n)
{
if (n == 1)
return 1;
else
return (n + triangle(n-1));
}
7.有20个结点的完全二叉树中，根结点在第0层，第4层有——个结点。
8.求最短路径的Di jkstra算法的时间复杂度为——。
9.每次从无序表中挑选一个最小或最大元素，把它交换到有序表的一端，这种排序方法叫
做——排序。
10.当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取
线性表中的元素时，应采用——存储结构。
三、算法题（共3题，20分）
1.阅读下列程序，完成如下任务：
（1）描述func的功能：（2分）
（2）将程序改写为递归方式。（4分）
int func(int n) {
int result = 0;
while(n > 0) {
result += n;
--n;
}
return result;
}
2.阅读下列二分查找的递归算法，填空。（6分，每空2分）
//说明
//在数组A中，在索引low至索引high范围内，查找与k相同的元素
//若查找成功，返回与k匹配的元素之索引
//否则返回-1
int BinarySearch(ElemType A[], int low, int high, ElemType k)
{
if ((1))
{
int mid = (low + high)/2;
if ( (2) ) //查找成功，返回元素的下标
return mid;
else if (k < A[mid])
return BinarySearch(A, low, mid – 1, k);//在左子表上继续上查找
else //在右子表上继续查找
return 3)
}
else
return -1; //查找失败，返回-1
}//end of function
(1) (2) (3)
3.若用二叉链表作为二叉树的存储表示，试针对以下问题编写递归算法。（8分）
算法要求：以二叉树为参数，交换每个结点的左子女的右子女。
四、应用题（共4题，30分）
1.已知一棵二叉树的先序遍历的结果是ABECDFGHIJ，中序遍历的结果是EBCDAFHIGJ，
（1）画出这棵二叉树。（5分）
（2）给出这棵二叉的后序遍历序列。（3分）
2.假定用于通信的电文公由8个字母c1,c2,c3,c4,c5,c7,c8组成，各字母在电文出现的频率
分别为5, 25, 3, 6, 10, 11, 36, 4。
（1）为这8个字母设计不等长Huffman编码（6分）
（2）计算该电文的总码长。（2分）
3.无资源
4.无资源
淋哥打的~~~
本科实验报告 课程名称：数据结构B 实验项目：查找 实验地点：行勉楼C214 专业班级：软件XXX班学号：2014XXXX 学生姓名：xxxxx 指导教师：牛之贤张润梁 2016年 1 月 1 日
void insertBST(BiTree *bt, BiTree s) { if (*bt == NULL) *bt = s; else if (s->data.key<(*bt)->data.key) insertBST(&((*bt)->lchild), s); else if (s->data.key>(*bt)->data.key) insertBST(&((*bt)->rchild), s); } main() { char ch; KeyType key; BiTree bt, s; int i = 0; printf("请输入元素：\n"); scanf("%d", &key); bt = NULL; while (key != -1) { s = (BiTree)malloc(sizeof(BiTNode)); (s->data).key = key; s->lchild = s->rchild = NULL; insertBST(&bt, s); scanf("%d", &key); } do { printf("输入你想要查找的元素："); scanf("%d", &key); s = searchBST(bt, key); if (s != NULL) printf("成功! 这个等价元素是 %d.\n", s->data.key); else printf("没有找到!\n"); printf("是否继续查找?(y/n)："); scanf("%c", &ch); ch = getchar(); } while (ch == 'y' || ch == 'Y'); getchar(); } 4.2#include
数据结构复习题 第一章概论 一、选择题 1、研究数据结构就是研究( D )。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作 2、算法分析的两个主要方面是( A )。 A. 空间复杂度和时间复杂度 B. 正确性和简单性C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是( D )。 A. 图 B. 树 C. 广义表 D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、( B )等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C )。 fori0;im;i++ forj0;jn;j++ a[i][j]i*j; A. Om2 B. On2 C. Om*n D. Om+n 6、算法是( D )。
A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 7、某算法的语句执行频度为(3n+nlog2n+n2+8),其时间复杂度表示( C )。 A. On B. Onlog2n C. On2 D. Olog2n 8、下面程序段的时间复杂度为( C )。 i1; whilein ii*3; A. On B. O3n C. Olog3n D. On3 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的( B )和运算等的学科。 A. 结构 B. 关系 C. 运算 D. 算法 10、下面程序段的时间复杂度是( A )。 is0; whilesn i++;s+i; A. On B. On2 C. Olog2n D. On3 11、抽象数据类型的三个组成部分分别为( A )。 A. 数据对象、数据关系和基本操作 B. 数据元素、逻辑结构和存储结构 C. 数据项、数据元素和数据类型 D. 数据元素、数据结构和数据类型 12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量,以下解释错误的是(D)。
习 9解答 判断题： 1．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。 答：FALSE (错。链表表示的有序表不能用折半查找法。) 2.有n 个数据放在一维数组A[1..n]中，在进行顺序查找时，这n 个数的排列有序或无序其平均查找长度不同。 答：FALSE (错。因顺序查找既适合于有序表也适合于无序表；对这两种表，若对于每个元素的查找概率相等，则顺序查找的ASL 相同，并且都是(n+1)/2；对于查找概率不同的情况，则按查找概率由大到小排序的无序表其ASL 要比有序表的ASL 小。) 3.折半查找是先确定待查有序表记录的范围，然后逐步缩小范围，直到找到或找不到该记录为止。( ) 答：TRUE 4.哈希表的查找效率主要取决于哈希表哈希表造表时选取的哈希函数和处理冲突的方法。 答：TRUE 5.查找表是由同一类型的数据元素(或记录)构成的集合。 答：TRUE 单选题： 6.对于18个元素的有序表采用二分(折半)查找，则查找A[3]的比较序列的下标为( )。 A. 1、2、3 B. 9、5、2、3 C. 9、5、3 D.9、4、2、3 答：D (第一次??2/)181(+ = 9,第二次??2/)81(+ = 4，第三次??2/)31(+ = 2, (第四次??2/)33(+ = 3，故选D. 7. 顺序查找法适合于存储结构为____________的线性表。 A.散列存储 B.顺序存储或链式存储 C.压缩存储 D.索引存储 答：B 8.对线性表进行二分查找时，要求线性表必须( )。 A ．以顺序方式存储 B. 以链接方式存储 C ．以顺序方式存储，且结点按关键字有序排序 D. 以链接方式存储，且结点按关键字有序排序 答：C 9.设哈希表长m=14，哈希函数为H(k) = k MOD 11。表中已有4个记录(如下图
1.矿井设计的依据分别为：设计任务书、地质资料、国家总的建设方针政策及有 关规程规定、经批准的上阶段确定的设计原则。 2.一部矿井初步设计文件应包括：初步设计说明书、初步设计主要机电设备和器材目 录、初步设计概算书、初步设计三材清册和附图 3.钢轨的组成部分为：轨头、轨腰、轨底。 4.道岔的组成部分为：尖轨、辙叉、转辙器、道岔曲轨、护轮轨、基 本轨。 5.大巷装车式采区下部车场的基本形式分别为：立式、卧式、斜式。 6.石门装车式采区下部车场的基本形式分别为：环形式、折返式。 7.采区甩车场高低道设计中，一般情况下，高低道的最大高差 H ≤ 0.5m ；高低道起坡 点间距L≤ 1~2m ； 8.《煤炭工业矿井设计规范》规定，井底车场通过能力应大于矿井设计生产能力 的 30% ；井底煤仓的有效容量是日产量的 0.15~0.25 倍，其中，大型矿井取 0.15 值，中型矿井取 0.25 值。 9.矿井设计生产能力划分为大、中、小型，大型矿井为 120万t/a 以上；中型矿井为 60 万t/a 、 90万t/a 、 45万t/a ；小型矿井为 30万t/a 以下。 10.井底车场中，固定式矿车的列车调车方式常见的有：顶推式调车、专用设备调 车、顶推拉调车、甩车调车。 11.矿用标准道岔分为单开道岔、对称道岔和渡线道岔。 2、轨距指的是两根轨 道内边缘之间的最短距离； 12.请回答道岔型号为ZDK615-4-12的以下几个问题：为单开道岔，其轨距 是 600 mm， 4 号道岔，道岔转弯半径为 12 m，轨型是 15 ㎏/m。 4、请回答道岔型号为ZDX622-4-1216的以下几个问题：为渡线道岔，其轨距是 600 mm， 4 号道岔，道岔转弯半径为 12 m，轨型是 22 ㎏/m，两轨道中心距 1.6 m。 13.采区下部车场按其装车位置，可分为石门装车、大巷装车和绕道装车。 14.采区下部车场按其绕道布置形式，可分为卧式布置、环形布置立式布置和斜式布 置。 15.采区下部车场按其绕道与大巷的位置，可分为顶板绕道、底板绕道和卧式绕 道。 16.采区车场线路由存车线线路、调车线线路和通过线线路组成； 17.采区中部甩车场按其甩入位置可分为甩入石门、甩入绕道和甩入大巷。 18.采区中部甩车场按其甩入方向数可分为单向甩和双向甩。 19.采区中部甩车场按其回转次数可分为一次回转和二次回转。 20.采区中部甩车场按其起坡轨道数可分为单道起坡和双道起坡。 21.采区上部车场有平车场、甩车场和转盘车场三种。 22.如果采区上下山位于煤层中，其上部车场一般为甩车场车场； 15、如果采区上山距 回风大巷较远，其上部车场一般选用平车场 23.采区上部平车场按其提升方向与进入车场方向的关系，可分为顺向平车场和逆 向平车场； 24.如果采区上山距区段回风平巷较远，其上部平车场一般选用顺向平车场 25.两个平面曲线间应加一段直线段，其长度一般≮2000㎜； 26.当采区上下山布置两条时，其之间的水平距离一般为 20-25 m ，布置三条时，其上下 山之间的水平距离为 10-15 m 27.现行基本建设前期工作程序包括：项目建议书、可行性研究报告、初步设计、开工报
四川大学期末考试试题 （2008-2009学年第1学期） 课程号：课程名称：数据结构与算法分析（B卷）任课教师： 1．数据类型为（）。 A）数据项的集合B）值的集合及定义在其上的一组操作的总称 C）数据元素的集合D）关键字的集合 2．链表不具有的特点是（）。 A）可随机直接访问任一元素B）插入删除不需要移动元素 C）不必事先估计元素个数D）所需空间与线性表长度成正比 3．设一个栈的入栈序列是ABCD，则借助于一个栈所得到的出栈序列不可能是（）。 A）ABCD B）DCBA C）ABCD D）DABC 4．将对称矩阵A nxn压缩存储在一维数组B[m]中，则m的值至少为（）。 A）n(n+1)/2 B）n(n-1)/2 C）n(n+1) D）n2 5．设二叉树中有n2个度为2的结点，n1个度为1的结点，n0个叶子结点，则此二叉树中空指针域个数为（）。 A）n0+n1+n2 B）n2+n1+2n0 C）2n2+n1D）2n0+n1 6．对于具有n个顶点的强连图，其弧条数的最小值为（）。 A）n+1 B）n C）n-1 D）n-2 7．一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有（）个结点。 A）2k-1-1 B）2k-1C）2k-1+1 D）2k-1 8．归并排序的时间复杂度是（）。 A）O(1) B）O(n) C）O(n2) D）O(nlogn) 9．每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是（）。 A）冒泡排序B）简单选择排序C）希尔排序D）直接插入排序10．按照二叉树的定义，具有3个结点的不同形态（相似）的二叉树有（）种。 A）3 B）4 C）5 D）6 二、（本题10分） 利用两个栈S1、S2模拟一个队列（如客户队列）时，如何用栈的运算实现队列的插入、删除运算，请简述算法思想。 三、（本题10分） 已知一棵二叉树的先序序列与中序序列分别如下，试画出此二叉树。 先序序列：ABCDEFGH IJ 中序序列：CBEDAGHFJI 注：试题字迹务必清晰，书写工整。本题2页，本页为第1页 教务处试题编号：
软件工程复习题 一、单选题 1、软件开发的结构化设计(SD)方法,全面指导模块划分的最重要原则应该是( c ) A模块高内聚B模块低耦合C模块独立性D程序模块化 2、软件工程方法的提出起源于软件危机,而其目的应该是最终解决软件的什么问题?( D ) A产生危机B质量保证C开发效率D生产工程化 3、软件工程开发的可行性研究是决定软件项目是否继续开发的关键,而可行性研究 的结论主要相关于( A) A软件系统目标B软件的性能 C软件的功能D软件的质量 4、软件需求分析一般应确定的是用户对软件的( D) A.功能需求 B.非功能需求 C.性能需求 D.功能需求和非功能需求 5、软件测试是满足软件的功能和性能要求,保证软件正确性的措施,一般软件测试 计划的制订应始于软件开发的哪个阶段? ( D) A.需求分析 B.软件设计 C.程序编码 D.软件计划 6、软件工程方法是在实践中不断发展的方法,而早期的软件工程方法主要是指( B ) A.原型化方法 B.结构化方法 C.面向对象方法. D.功能分解法 7、数据流图描述数据在软件中流动和被处理变换的过程,它是以图示的方法来表示,即.( A ) A.软件模型 B.软件功能 C.软件结构 D.软件加工 8、软件工程学涉及到软件开发技术和工程管理两方面的内容,下述内容中哪一个不 属于开发技术的范畴?（D） A.软件开发方法 B.软件开发工具 C.软件工程环境 D.软件工程经济 9、软件文档是软件工程实施中的重要成份,它不仅是软件开发的各阶段的重要依 据,而且也影响软件的（） A.可理解性 B.可维护性 C.可扩展性 D.可靠性 10、从( )语言开始,软件摆脱了对硬件的依赖。 A.第一代 B.第二代 C.第三代 D.第四代 11、在下面列出的基本成分中,哪个不是实体关系图的基本成分? ( ) A.实体 B.数据存储 C.关系D属性 12、结构化程序设计主要强调程序的（C） A.效率 B.速度 C.可读性 D.大小
数据结构模拟试题... 一、简答题（15分，每小题3分） 1.简要说明算法与程序的区别。 2.在哈希表中，发生冲突的可能性与哪些因素有关？为什么？ 3.说明在图的遍历中，设置访问标志数组的作用。 4.说明以下三个概念的关系：头指针，头结点，首元素结点。 5.在一般的顺序队列中，什么是假溢出？怎样解决假溢出问题？ 二、判断题（10分，每小题1分） 正确在括号内打√，错误打× ( )（1）广义表((( a ), b), c ) 的表头是(( a ), b)，表尾是( c )。 ( )（2）在哈夫曼树中，权值最小的结点离根结点最近。 ( )（3）基数排序是高位优先排序法。 ( )（4）在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1。 ( )（5）在单链表中，给定任一结点的地址p，则可用下述语句将新结点s插入结点p的后面：p->next = s; s->next = p->next; ( )（6）抽象数据类型（ADT）包括定义和实现两方面，其中定义是独立于实现的，定义仅给出一个ADT的逻辑特性，不必考虑如何在计算机中实现。 ( )（7）数组元素的下标值越大，存取时间越长。 ( )（8）用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。 ( )（9）拓扑排序是按AOE网中每个结点事件的最早发生时间对结点进行排序。 ( )（10）长度为1的串等价于一个字符型常量。 三、单项选择题（10分, 每小题1分） 1．排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这是哪种排序方法的基本思想？ A、堆排序 B、直接插入排序 C、快速排序 D、冒泡排序 2．已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应该： A）将邻接矩阵的第i行删除B）将邻接矩阵的第i行元素全部置为0 C）将邻接矩阵的第i列删除D）将邻接矩阵的第i列元素全部置为0 3．有一个含头结点的双向循环链表，头指针为head, 则其为空的条件是： A.head->priro==NULL B. head->next==NULL C. head->next==head D. head->next-> priro==NULL 4. 在顺序表( 3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30 ) 中，用折半法查找关键码值11，所需的关键码比
一、选择题 1. 算法的计算量的大小称为计算的（）。 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（） A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 4．一个算法应该是（）。A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C. 5. 下面关于算法说法错误的是（） A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（）(1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。 A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？ A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（）】 A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（）】 FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A．O(2n) B．O(n) C．O(n2) D．O(log2n) 12．程序段FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF A[j]>A[j+1] THEN A[j]与A[j+1]对换； 其中n为正整数，则最后一行的语句频度在最坏情况下是（） A. O（n） B. O(nlogn) C. O(n3) D. O(n2) 】 13．以下哪个数据结构不是多型数据类型（）】 A．栈B．广义表C．有向图D．字符串 14．以下数据结构中，（）是非线性数据结构】
《数据结构与算法》章节测试题与答案 课程简介：数据结构是一门面向设计，且处于计算机学科核心地位的技术基础和主干必修课，也是算法分析与…… 课程简介：数据结构是一门面向设计，且处于计算机学科核心地位的技术基础和主干必修课，也是算法分析与设计、操作系统、编译技术、计算机图形与图像处理等专业课程的先修课程。 引论 1.【单选题】1.在数据结构中,从逻辑上可以把数据结构分成( )。 A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 答案：C 2.【单选题】2. 在数据结构中,从存储结构上可以将之分为( )。 A、动态结构和静态结构
B、顺序存储和非顺序存储 C、紧凑结构和非紧凑结构 D、线性结构和非线性结构 答案：B 3.【单选题】3. 某算法的时间复杂度是O(n^2),表明该算法的( )。 A、执行时间与n^2成正比 B、问题规模是n^2 C、执行时间等于n^2 D、问题规模与n^2成正比 答案：A 4.【单选题】4. 在下面的程序段中,x=x+1;的语句频度为( )。for( i=1;i<=n;i++) for( j=1;j<=n;j++) x=x+1; A、O(2n) B、O(n) C、O(n^2)
D、O(log2n) 答案：C 5.【单选题】5. 以下数据结构中,( )是非线性数据结构。 A、树 B、字符串 C、队 D、栈 答案：A 6.【单选题】6. 顺序存储,存储单元的地址( )。 A、一定连续 B、一定不连续 C、不一定连续 D、部分连续,部分不连续 答案：A 7.【单选题】7.评价一个算法性能好坏的重要标准是( )。
1．面向对象程序设计将数据与A放在一起，作为一个相互依存、不可分割的整体来处理。A．对数据的操作 B. 信息 C. 数据隐藏 D. 数据抽象 2．下面关于对象概念的描述中，A是错误的。 A. 对象就是C语言中的结构体变量 B. 对象代表这正在创建的系统中的一个实体 C. 对象是一个状态和操作（或方法）的封装体 D. 对象之间的信息传递是通过消息进行的 3．C++对C语言作了很多改进，从面向过程变成为面向对象的主要原因为D。 A. 增加了一些新的运算符 B. 允许函数重载，并允许设置缺省参数 C. 规定函数说明符必须用原型 D. 引进了类和对象的概念 4. 在下列关键字中，用以说明类中公有成员的是A。 A. public B. private C. protected D. friend 5. D是一个类的多个对象共享的。 A. 公有数据成员 B. 私有数据成员 C. 保护数据成员 D. 静态数据成员 6．对定义重载函数的下列要求中， D 是错误的。 A. 要求参数的个数不同 B. 要求参数中至少有一个类型不同 C. 要求参数个数相同是，参数类型不同 D. 要求函数的返回值不同 7. 关于成员函数特征的下述描述中，____A____是错误的。 A.一定是内联函数 B.可以重载 C.可以设置缺省参数 D.可以是静态的 8．下列的各类函数中，C不是类的成员函数。 A. 构造函数 B. 析构函数 C. 友元函数 D. 拷贝初始化构造函数 9. 下列不能作为类的成员的是B。 A. 自身类对象的指针 B. 自身类对象 C.自身类对象的引用 D.另一个类的对象 10. 下述静态成员的特性中，D是错误的。 A. 说明静态数据成员时前面要加修饰符static B. 静态数据成员要在类体外进行初始化 C. 引用静态数据成员，要在静态数据成员名前加<类名>和作用域运算符 D. 静态数据成员不是所有对象所共用的 11．已知类Sample中的一个成员函数说明如下：void set(Sample &a); 其中，Sample &a 的含义是C 。 A. 指向类Sample的指针a B. 将a的地址值赋给变量set C. a是类Sample的对象引用，用来作函数set()的形参 D. 变量Sample与a按位相与作为函数set()的参数 12、下列表示引用的方法中，A 是正确的。已知：int m=10; A. int &x=m; B. int &y=10; C. int &z; D. float &t=&m; 13、关于delete运算符的下列描述中，( C )是错误的。 A.它必须用于new返回的指针； B.它也适用于空指针； C.对一个指针可以使用多次该运算符； D.指针名前只有一对方括号符，不管所删除数组的维数。
实验一线性表 一．目的与要求 本次实习的主要目的是为了使学生熟练掌握线性表的基本操作在顺序存储结构和链式存储结构上的实现，提高分析和解决问题的能力。要求仔细阅读并理解下列例题，上机通过，并观察其结果，然后独立完成后面的实习题。 二．例题 问题描述: 用链表形式存储一个字符串，插入、删除某个字符，最后按正序、逆序两种方式输出字符串。 输入: 初始字符串，插入位置，插入字符，删除字符。 输出: 已建立链表（字符串），插入字符后链表，删除字符后链表，逆转后链表。 存储结构: 采用链式存储结构 算法的基本思想: 建立链表当读入字符不是结束符时，给结点分配存储空间，写数据域，将新结点插到表尾；插入字符：根据读入的字符在链表中找插入位置，将新结点插入到该位置之前；删除字符：根据读入的删除字符在链表中找到被删结点后，将其从链表中删除；链表逆转：从链表的第一个结点开始对所有结点处理，将每个结点的前驱变为它的后继；打印链表：从链表的第一个结点开始，依次打印各 [运行情况] Input a linktable(a string):abcde↙ Build link is :abcde Please input a char you want to insert after:b↙ Please input a char you want to insert:c↙ After p insert y,link is:abccde Please input a char you want to delete:e↙ after delete p,link is:abccd Opsite result is :dccba 如图显示：
数据结构与算法试题 一、单选题 1、在数据结构的讨论中把数据结构从逻辑上分为 (C ) A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。 2、采用线性链表表示一个向量时,要求占用的存储空间地址(D ) A 必须就是连续的 B 部分地址必须就是连续的 C 一定就是不连续的 D 可连续可不连续 3、采用顺序搜索方法查找长度为n的顺序表时,搜索成功的平均搜索长度为( D )。 A n B n/2 C (n-1)/2 D (n+1)/2 4、在一个单链表中,若q结点就是p结点的前驱结点,若在q与p之间插入结点s,则执行( D )。 A s→link = p→link;p→link = s; B p→link = s; s→link = q; C p→link = s→link;s→link = p; D q→link = s;s→link = p; 5、如果想在4092个数据中只需要选择其中最小的5个,采用( C )方法最好。 A 起泡排序 B 堆排序 C 锦标赛排序 D 快速排序 6、设有两个串t与p,求p在t中首次出现的位置的运算叫做( B )。 A 求子串 B 模式匹配 C 串替换 D 串连接 7、在数组A中,每一个数组元素A[i][j]占用3个存储字,行下标i从1到8,列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中,则存放该数
组至少需要的存储字数就是( C )。 A 80 B 100 C 240 D 270 8、将一个递归算法改为对应的非递归算法时,通常需要使用( A )。 A 栈 B 队列 C 循环队列 D 优先队列 9、一个队列的进队列顺序就是1, 2, 3, 4,则出队列顺序为( C )。 10、在循环队列中用数组A[0、、m-1] 存放队列元素,其队头与队尾指针分别为front与rear,则当前队列中的元素个数就是( D )。 A ( front - rear + 1) % m B ( rear - front + 1) % m C ( front - rear + m) % m D ( rear - front + m) % m 11、一个数组元素a[i]与( A )的表示等价。 A *(a+i) B a+i C *a+i D &a+i 12、若需要利用形参直接访问实参,则应把形参变量说明为( B )参数。 A 指针 B 引用 C 值 D 变量 13、下面程序段的时间复杂度为( C ) for (int i=0;i 实验报告 课程名称：数据结构B 实验项目：顺序表 实验地点：实验楼110 专业班级：计科1301班学号：2013001989 学生姓名：杨喆 指导教师：孟亮 2015年1 月1 日 一、实验目的和要求 本次实习的主要目的是为了使学生熟练掌握线性表的基本操作在顺序存储结构和链式存储结构上的实现，提高分析和解决问题的能力。 要求仔细阅读并理解下列例题，上机调试并编译执行通过，并观察其结果，然后独立完成后面的实验内容，写出完整的实验报告。编写程序过程中注意养成良好的编程风格与习惯，要求程序结构清晰，程序缩进，适当注释。 二、实验内容和原理 1．设顺序表A中的数据元素递增有序，试写一程序，将x插入到顺序表的适当位置上，使该表仍然有序。 2．用单链表ha 存储多项式A（x ）=a0+a1x1+a2x2+…+a n x n(其中a I为非零系数)，用单链表hb 存储多项式B（x ）=b0+b1x1+b2x2+…+b m x m(其中b j为非零系数)，要求计算C（x ）= A（x ）+B（x ），结果存到单链表hc中。试写出程序。 3．设有n个人围坐在一个圆桌周围，现从第s个人开始报数，数到第m的人出列，然后从出列的下一个人重新开始报数，数到m的人又出列，如此重复，直到所有的人全部出列为止。Josephus问题是：对于任意给定的n，m，s，求出按出列次序得到的n个人员的顺序表。 三、主要仪器设备 1.设备: PC微机; 2.实验环境: windows操作系统；VC++6.0, 四、实验结果与分析（必填） （1）程序清单： 实验1_1: #include "stdio.h" #include "malloc.h" #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define LIST_INIT_SIZE 80 #define LISTINCREMENT 10 typedef int Status; typedef int ElemType; typedef struct { ElemType *elem; XXXXXX学校2014--2015学年第一学期期末考试 2014级计算机应用专业《数据结构与算法》试题A卷 2015年01月19日 注意： 本试卷共4页，满分100分，考试时间为90分钟，考试方式为闭卷笔试。 姓名：______________________ 学号：________________________ 一、选择题（每题1分，共31题，第31题2分，总32分） （1）设有如下遗产继承规则：丈夫和妻子可以互相继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。表示该遗产继承关系最合适的数据结构应该是（）。 A.树 B.图 C.数组 D.二叉树（2）在数据结构中，从逻辑上可以把数据结构分成（）。 A.动态结构和静态结构 B. 紧凑结构和非紧凑结构 C.线性结构和非线性结构 D. 内部结构和外部结构 （3）以下数据结构中不属于线性数据结构的是（）。 A.队列 B.线性表 C.二叉树 D.栈 （4）算法的时间复杂度是指（）。 A.执行算法程序所需要的时间 B. 算法程序的长度 C.算法执行过程中所需要的基本运算次数 D. 算法程序中的指令条数（5）算法一般可以由哪几种控制结构组合而成（）。 A.循环、分支、递归 B. 顺序、循环、嵌套 C. 循环、递归、选择 D. 顺序、选择、循环 （6）计算机算法指的是解决问题的步骤序列，它必须具备（）这三个特性。 A. 可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C.确定性、有穷性、稳定性 D. 易读性、稳定性、安全性（7）在单向循环链表中，若头指针为h，那么p所指结点为尾结点的条件是（）。 A. p=NULL B. p→next=NULL C. p=h D. p→next=h （8）带头结点的单链表head为空的判定条件是（）。 A. head = = NULL B. head → next = = NULL C. head → next = = head D. head ！= NULL （9）对于栈操作数据的原则是（）。 A.先进先出 B. 后进先出 C. 后进后出 D. 不分顺序（10）有六个元素按6,5,4,3,2,1的顺序进栈，问下列哪一个不是合法的出栈序列？（） A.5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 （11）栈s最多能容纳4个元素。现有6个元素按A,B,C,D,E,F的顺序进栈，问下列哪一个序列是可能的出栈序列？（） A.E,D,C,B,A,F B. B,C,E,F,A,D C.C,B,E,D,A,F D. A,D,F,E,B,C （12）设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作，则下面得不到的序列为（）。 A. fedcba B. bcafed C.dcefba D. cabdef （13）输入序列为ABC,可以变为CBA时，经过的栈操作为（）。 A.push，pop，push，pop，push，pop B. push，push，push，pop， pop，pop C. push，push，pop， pop，push，pop D. push，pop，push，push，pop， pop （14）已知串S=’aaab’，其next数组值为（）。 A. 0123 B. 1123 C. 1231 D.1211 （15）串”ababaaababaa”的next数组为（）。 A. 012345678999 B. 012121111212 C. 011234223456 D. 0123012322345 （16）若串S=”software”，其子串的数目是（）。 A. 8 B. 37 C. 36 D. 9 《人工智能》课程习题 第一章绪论 1-1. 什么是人工智能？试从学科和能力两方面加以说明。 1-2. 在人工智能的发展过程中，有哪些思想和思潮起了重要作用？ 1-3. 为什么能够用机器（计算机）模仿人的智能？ 1-4. 现在人工智能有哪些学派？它们的认知观是什么？ 1-5. 你认为应从哪些层次对认知行为进行研究？ 1-6. 人工智能的主要研究和应用领域是什么？其中，哪些是新的研究热点？ 第二章知识表示方法 2-1状态空间法、问题归约法、谓词逻辑法和语义网络法的要点是什么？它们有何本质上的联系及异同点? 2-2设有3个传教士和3个野人来到河边，打算乘一只船从右岸渡到左岸去。该船的负载能力为两人。在任何时候，如果野人人数超过传教士人数，那么野人就会把传教士吃掉。他们怎样才能用这条船安全地把所有人都渡过河去? 2-3利用图2.3，用状态空间法规划一个最短的旅行路程：此旅程从城市A开始，访问其他城市不多于一次，并返回A。选择一个状态表示，表示出所求得的状态空间的节点及弧线，标出适当的代价，并指明图中从起始节点到目标节点的最佳路径。 2-4试说明怎样把一棵与或解树用来表达图2.28所示的电网络阻抗的计算。单独的R、L 或C可分别用R、jωL或1/jωC来计算，这个事实用作本原问题。后继算符应以复合并联和串联阻抗的规则为基础。 图 2.28 2-5试用四元数列结构表示四圆盘梵塔问题，并画出求解该问题的与或图。 2-6把下列句子变换成子句形式： (1) ( x)｛P(x)→P(x)｝ (2) ?x?y(On(x,y)→Above(x,y)) (3) ?x?y?z(Above(x,y)∧Above(y,z)→Above(x,z)) (4) ～｛(?x)｛P(x)→｛（?y）［p(y)→p(f(x,y))］∧(?y)［Q(x,y)→P(y)］｝｝｝ 2-7用谓词演算公式表示下列英文句子(多用而不是省用不同谓词和项。例如不要用单一的谓词字母来表示每个句子。) A computer system is intelligent if it can perform a task which,if performed by a human, requires intelligence. 2-8把下列语句表示成语义网络描述： (1) All man are mortal. (2) Every cloud has a silver lining. (3) All branch managers of DEC participate in a profit-sharing plan. 2-9作为一个电影观众，请你编写一个去电影院看电影的剧本。 2-10试构造一个描述你的寝室或办公室的框架系统。 第三章搜索推理技术 3-1什么是图搜索过程?其中，重排OPEN表意味着什么，重排的原则是什么? 3-2试举例比较各种搜索方法的效率。 3-3化为子句形有哪些步骤?请结合例子说明之。 3-4如何通过消解反演求取问题的答案? 3-5什么叫合适公式?合适公式有哪些等价关系? 3-6用宽度优先搜索求图3.33所示迷宫的出路。 图 3.33 迷宫一例 3-7用有界深度优先搜索方法求解图3.34所示八数码难题。 2 8 1 2 3 1 6 3 8 4 7 5 4 7 6 5 一、单项选择题 1 某算法的时间复杂度是O(n 2 ) ，表明该算法（）。 A 问题规模是n2 B 问题规模与n2成正比 C 执行时间等于n2 D 执行时间与n2成正比 2、关于数据结构的描述，不正确的是（）。 A数据结构相同，对应的存储结构也相同。 B数据结构涉及数据的逻辑结构、存储结构和施加其上的操作等三个方面。 C数据结构操作的实现与存储结构有关。 D定义逻辑结构时可不考虑存储结构。 3、按排序策略分来，起泡排序属于（）。 A插入排序B选择排序C交换排序D归并排序 4、利用双向链表作线性表的存储结构的优点是（）。 A便于进行插入和删除的操作 B 提高按关系查找数据元素的速度 C节省空间D便于销毁结构释放空间 5、一个队列的进队顺序为1,2,3,4，则该队列可能的输出序列是（）。 A 1,2,3,4 B 1,3,2,4 C 1,4,2,3 D 4,3,2,1 6、 Dijkstra算法是按（）方法求出图中从某顶点到其余顶点最短路径的。 A按长度递减的顺序求出图的某顶点到其余顶点的最短路径 B按长度递增的顺序求出图的某顶点到其余顶点的最短路径 C通过深度优先遍历求出图中从某顶点到其余顶点的所有路径 D通过广度优先遍历求出图的某顶点到其余顶点的最短路径 7、字符串可定义为n（ n≥ 0）个字符的有限（）。其中，n是字符串的长度，表明字符串中字符的个数。 A集合B数列C序列D聚合 8、在二维数组A[9][10]中，每个数组元素占用 3 个存储单元，从首地址SA 开始按行连续存放。在这种情况下，元素A[8][5]的起始地址为（）。 A SA+141 B SA+144 C SA+222 D SA+255 9、已知广义表为L(A(u,v,(x,y),z),C(m,(),(k,l,n),(())),((())),(e,(f,g),h))，则它的长度是（）。 A2B3C4D5 10.对于具有n(n>1)个顶点的强连通图，其有向边条数至少有_____。 A. n+1 B. n C. n-1 D. n-2 11.一个递归算法必须包括 __________ 。 A. 递归部分 B . 结束条件和递归部分 C. 迭代部分 D. 结束条件和迭代部分 12.从逻辑上看可以把数据结构分为__________两大类。 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 13、若在长度为n 的顺序表的表尾插入一个新元素的渐进时间复杂度为（）。 A O(n) B O(1) C O(n 2) D O(log 2n) 14.采用顺序搜素方式搜索长度为 n 的线性表时，在等概率情况下，搜索成功时的平均搜索 长度为 __________。 A. n B. n/2 C . (n+1)/2 D. (n-1)/2 15、非空的循环单链表first的链尾结点（由p 所指向）满足（）。 A p->link==NULL; B P==NULL; 第一章绪论 一．选择题 1．数据结构被形式地定义为（K，R），其中K是①_B_的有限集合，R是K上的②_D_的有限集合。 ①A．算法B．数据元素C．数据操作D．逻辑结构 ②A．操作B．映象C．存储D．关系 2．算法分析的目的是①C，算法分析的两个主要方面是②A。 ①A．找出数据结构的合理性 B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进 D．分析算法的易懂性和文档性 ②A．空间复杂性和时间复杂性 B．正确性和简明性 C．可读性和文档性 D．数据复杂性和程序复杂性 3．在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为(B) A．逻辑结构B．顺序存储结构 C．链表存储结构D．以上都不对 4．数据结构中，在逻辑上可以把数据结构分成：( C ）。 A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构5．以下属于顺序存储结构优点的是（A ）。 A．存储密度大B．插入运算方便 C．删除运算方便D．可方便地用于各种逻辑结构的存储表示 6．数据结构研究的内容是（D ）。 A．数据的逻辑结构B．数据的存储结构 C．建立在相应逻辑结构和存储结构上的算法D．包括以上三个方面 7．链式存储的存储结构所占存储空间（A ）。 A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B．只有一部分，存放结点值 C．只有一部分，存储表示结点间关系的指针 D．分两部分，一部分存放结点值，另一部分存放结点所占单元数 8．一个正确的算法应该具有5 个特性，除输入、输出特性外，另外3 个特性是（A ）。 A．确定性、可行性、有穷性B．易读性、确定性、有效性C．有穷性、稳定性、确定性D．可行性、易读性、有穷性9．以下关于数据的逻辑结构的叙述中正确的是（A）。 A．数据的逻辑结构是数据间关系的描述 B．数据的逻辑结构反映了数据在计算机中的存储方式 C．数据的逻辑结构分为顺序结构和链式结构 D．数据的逻辑结构分为静态结构和动态结构 10．算法分析的主要任务是（C ）。 A．探讨算法的正确性和可读性B．探讨数据组织方式的合理性C．为给定问题寻找一种性能良好的解决方案D．研究数据之间的逻辑关系 二．解答 设有一数据的逻辑结构为：B=(D, S)，其中： D={d1, d2, …, d9} S={太原理工数据结构实验报告 实验一 顺序表
《数据结构与算法》期末试题试卷A
太原理工大学人工智能复习题-试题-答案资料
算法与数据结构题库与答案
数据结构与算法习题库(考前必备)
相关主题
文本预览