共 8 页 第1页 南京工程学院试卷（样）
2010 /2011 学年 第 2 学期
课程所属部门： 计算机工程学院 课程名称： 数据结构
考试方式： 闭卷 使用班级： 计算机专业2009级各班
命题人：叶核亚、黄纬 教研室主任审核： 主管领导批准：
SString s1("aababbabac"),s2("aba");，执行下列语句后，
s1字符串是______________s1.replaceAll(s1.substring(0,1),s2); s1.removeAll(s2.substring(0,2));
南京工程学院
试题评分标准及参考答案(样)
共7页第1 页2010 / 2011 学年第 2 学期
南京工程学院评分标准及参考答案 共7页 第 3 页
0193
217356442578关键字序列delta =4
615742*8
2519191542*257817564293delta =2
191542*175625784293
delta =1
1517192542*42567893
南京工程学院评分标准及参考答案共7页第4 页
南京工程学院评分标准及参考答案
共7页第5 页
南京工程学院评分标准及参考答案共7页第6 页
南京工程学院评分标准及参考答案共7页第7 页
《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 单项选择题1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 、 1. 对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为 (c )。 (A)、正确性但).可行性(C).健壮性 2 ?设S为C语言的语句,计算机执行下面算法时， for(i=n-1 ; i>=0; i--) for(j=0 ; jvi; j++) (A)、n2(B). O(nlgn) 3?折半查找法适用于( a (D). 输入性 算法的时间复杂度为(d S； (C). O(n) (D). )。 O(n2) (A)、有序顺序表(B)、有序单链表 (C)、有序顺序表和有序单链表都可以 4 .顺序存储结构的优势是( d )。 (A)、利于插入操作(B)、利于删除操作 (C)、利于顺序访问(D)、利于随机访问 5. 深度为k的完全二叉树，其叶子结点必在第 (A)、k-1 ( B)、k (C)、k-1 和 6. 具有60个结点的二叉树，其叶子结点有 (A)、11 ( B)、13 ( C)、48 (D)、无限制 c )层上。 (D)、1 至 k 12个，则度过1 (D)、37 k 的结点数为( 7 .图的Depth-First Search(DFS) 遍历思想实际上是二叉树( 法的推广。 (A)、先序(B)、中序(C)、后序(D)、层序 8.在下列链队列Q中，元素a出队的操作序列为( a )遍历方 front (A )、 (B )、 (C)、 (D )、p=Q.front->next; p->next= Q.front->next; p=Q.front->next; Q.front->next=p->next; p=Q.rear->next; p->next= Q.rear->next; p=Q->next; Q->next=p->next; 9. Huffman树的带权路径长度WPL等于( (A)、除根结点之外的所有结点权值之和(C)、各叶子结点的带权路径长度之和(B) 、 ) 所有结点权值之和 根结点的值 b ■
实验一线性表的顺序存储实验 一、实验目的 1、掌握用Visual C++6.0上机调试顺序表的基本方法 2、掌握顺序表的基本操作，插入、删除、查找等算法的实现 二、实验内容 1、顺序表基本操作的实现 [问题描述] 当我们要在顺序表的第i个位置上插入一个元素时，必须先将顺序表中第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。 [基本要求] 要求生成顺序表时，可以键盘上读取元素，用顺序存储结构实现存储。 实验二单链表实验 一、实验目的 1、掌握用Visual C++6.0上机调试单链表的基本方法 2、掌握单链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现 二、实现内容 1、单链表基本操作的实现 [问题描述]要在带头结点的单链表h中第i个数据元素之前插入一个数据元素x ，首先需要在单链表中寻找到第i-1个结点并用指针p
指示，然后申请一个由指针s 指示的结点空间，并置x为其数据域值，最后修改第i-1个结点，并使x结点的指针指向第i个结点，要在带头结点的单链表h中删除第i个结点，首先要计数寻找到第i个结点并使指针p指向其前驱第i-1个结点，然后删除第i个结点并释放被删除结点空间。 [基本要求]用链式存储结构实现存储 [实现提示]链式存储结构不是随机存储结构，即不能直接取到单链表中某个结点，而要从单链表的头结点开始一个一个地计数寻找。 2、求表长以及有序单链表的合并算法的实现 [问题描述] 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并计算表长。要求利用原来两个单链表的结点存放归并后的单链表。 [基本要求]用链式存储结构实现存储 实验三栈的实现及应用 一、实验目的 1、掌握顺序栈的类型定义方法。 2、掌握在顺序栈上实现的六种基本算法。 2、掌握顺序栈的简单应用。 二、实验内容
数据结构试题及答案 一、单项选择题 (1)一个算法应该就是（)。 A)程序???B）问题求解步骤得描述 C）要满足五个基本属性??D) A与C (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)下列程序得时间复杂度为（) i=０；s＝０; wｈｉlｅ(s 共 6 页 第1页 南京工程学院试卷（A ） 2010 /2011 学年 第 1 学期 课程所属部门： 通信工程 课程名称： 通信网 考试方式： 开卷 使用班级： 无线通信071、光纤通信0711 命 题 人： 杨小伟 教研室主任审核： 主管领导批准： 题号 一 二 三 四 五 六 总分 得分 一、简答题（本题6小题，每小题5分，共30分） 1、简述现代通信网个组成结构？ 通信网的组成结构有从水平和垂直两种。（2分）现代通信网根据网络功能从水平方向上可以划分为三层， 即用现代户驻地网、接入网与核心网。现代通信网根据网络功能从垂直方向上可划分为传送网、业务网和应用层，以及支持全部三个层面的工作的支撑网。如图 2、简述我国电力通信网各级网的通信职责范围？为何下级网接入上一级网要采用两点接入方式？ 我国电力通信网分五级。一级通信网指由国家电网公司至各大区电网公司、各直属单位的通信电路；二级通信网指由大区电网公司至所属各省电力公司、各直属单位的通信电路；三级通信网由省电力公司至各市供电公司、各省直属单位的通信电路以及各市供电公司之间（包括500kV 变电站）的通信电路组成；四级通信网由市供电公司至所管辖各县供电公司、变电站、供电营业所、辖区内发电厂的通信电路以及县供电公司之间（包括220kV 变电站）的通信电路组成；五级通信网由县供电公司至所管辖各变电站以 及辖区内发电厂的通信电路组成。五级通信网又称为农村电力通信网。 下级网接入上一级网采用两点接入方式的目的是提高网络的安全和可靠性，在一个接入节点出现故障时仍能保证网络的正常运行 本题 得分 班级 学号 姓名 北京师范大学2011～2012学年第 1 学期期末考试试卷（A 卷） 课程名称： 数据结构 任课教师姓名： 刘玉铭 卷面总分： 100 分 考试时长： 100 分钟 考试类别：闭卷 院（系）： 数学科学学院 专 业： 年级： 2010 姓 名： 学 号： 阅卷教师（签字）： 一、 单项选择题（每题2分，共10题20分） 1．以下那一个术语与数据的存储结构无关？ 。 A ．栈 B ．哈希表 C ．线索树 D ．双向链表 2．链表不具有的特点是 。 A ．插入、删除不需要移动元素 B ．可随机访问任一元素 C ．不必事先估计存储空间 D ．所需空间与线性表长度成正比 3．算术表达式a+b*（c+d/e ）转为后缀表达式后为 。 A ．ab+cde/* B ．abcde/+*+ C ．abcde/*++ D ．abcde*/++ 4．二维数组A[10][20]采用列优先的存储方法,若每个元素占2个存储单元，设A[0][0]的地址为100，则元素A[7][6]的存储地址为 。 A ．232 B ．234 C ．390 D ．392 装 订 线 5．若一棵二叉树具有10 个度为2 的结点，5 个度为1 的结点，则度为0 的结点个数是。 A．9 B．11 C．15 D．不确定 6．一棵二叉树中序序列为FEABDC，后序序列为FBADCE，则层序序列为。 A. ABCDEF B. EFCDBA C. FECDAB D. EFCDAB 7．在有向图G 的拓扑序列中，若顶点Vi 在顶点Vj 之前，则下列情形不可能出现的是。 A．G 中有弧 数据结构试卷（一） 一、单选题（每题2 分，共20分） 1.栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在 676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。 A．688 B．678 C．692 D．696 5.树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6.二叉树的第k层的结点数最多为( ). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 7.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二 分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 8.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为 A. O（1） B. O（n） C. O（1og2n） D. O（n2） 9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K） =K %9作为散列函数，则散列地址为1的元素有（）个， A．1 B．2 C．3 D．4 10.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 二、填空题（每空1分，共26分） 1.通常从四个方面评价算法的质量：_________、_________、_________和_________。 2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。 3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数 为__________个，树的深度为___________，树的度为_________。 4.后缀算式9 2 3 +- 10 2 / -的值为__________。中缀算式（3+4X）-2Y/3对应的后缀算式 为_______________________________。 5.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指 针。在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有________________个指针是空指针。 6.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点 分别有_______个和________个。 7.AOV网是一种___________________的图。 8.在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有 向完全图中，包含有________条边。 9.假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元 素成为一个子表，则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。 《数据结构》题库及答案 一、选择题 1．线性表的顺序存储结构是一种 的存储结构，线性表的链式存储结构是一种 的存储结构。 a. 随机存储； b.顺序存储； c. 索引存取； d. HASH 存取 2．一个栈的入栈序列是a,b,c,d,e ，则栈的不可能的输出序列是 。 a. edcba; b. decba; c. dceab; d.abcde 3．一个队列的入队序列是1，2，3，4，则队列的输出序列是 。 a. 4,3,2,1; b. 1,2,3,4; c. 1,4,3,2; d.3,2,4,1 4．在一个单链表中，已知p 结点是q 结点的直接前驱结点，若在p 和q 之间插入结点s ，则执行的操作是 。 a. s->nxet=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; 5．设有两个串p,q ，求q 在p 中首次出现的位置的运算称作 。 a.联接 b.模式匹配 c.求子串 d.求串长 6．二维数组M 的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i 的范围从0到8，列下标j 的范围从1到10，则存放M 至少需要 个字节。 a. 90 b.180 c.240 d.540 7．在线索二叉树中，结点p 没有左子树的充要条件是 。 a. p->lch==NULL b. p->ltag==1 c. p->ltag==1且p->lch=NULL d. 以上都不对 8．在栈操作中，输入序列为（A ，B ，C ，D ），不可能得到的输出序列为：______ A 、（A ， B ， C ， D ） B 、（D ，C ，B ，A ） C 、（A ，C ，D ，B ） D 、（C ，A ，B ，D ） 9．已知某二叉树的后序序列是dabec ，中序序列是debac ，则它的先序序列是 。 A 、acbed B 、decab C 、deabc D 、cedba 10．设矩阵A 是一个对称矩阵，为了节省存储空间，将其下三角部分（见下图）按行序存放在一维数组B[1..n(n-1)/2]中，对任一上三角部分元素)(j i a ij ，在一维数组B 的存放位置是 。 试卷3 一、单项选择题(共20小题；每小题1分，共20分) 1、下列常量不合法的是（）。 A．1.5E-2 B．‘BASIC’C．0x12 D．“\\good” 2、下列变量名中不合法的是（）。 A．iCount B．Stu_NO C．INT D．vc++ 3、设变量已正确定义并赋值，以下正确的表达式是（）。 A．b=7++ B．x=3,++y C．a=7%3.0 D．x=y+1=2 4、表达式sizeof(double)-sizeof(3.1f)+3/2的值是（）。 A．4 B．5 C．5.5 D．1.5 5、下列各语句序列判别变量a、b的大小，若a 东华理工大学2015 —2016学年第 一 学期考试 模拟试卷 A 一、 填空题（50分） 1、数据结构是一门研究非数值计算的程序设计问题中的 数据元素 以及它们之间 关系 和运算等的科学。（2分） 2、数据结构的类型通常分为： 集合、线性结构、树形结构、图状结构或网状结构 ；从逻辑上可以把它们分成： 线性结构和非线性结构 。 3、数据的 逻辑结构 只抽象反映数据元素的 逻辑关系 ；数据的 存储（物理）结构 是数据的逻辑结构 在计算机存储器中的实现 。 4、算法分析的目的是分析算法的 效率以求改进 ，算法分析的两个主要方面是 空间复杂度和时间复杂度 。 A 5、计算机算法是解决问题的 有限运算序列 ，它必须具备 输入、输出、确定性、有穷性和稳定性 等5个方面的特性。 6、线性结构中元素之间的关系存在 一对一 关系，树形结构中元素之间的关系存在 一对多 关系，图形结构中元素之间的关系存在 多对多 关系。 7、试写出以下算法的时间复杂度 i=s=0 while (s i = i*2 O(log2n) 8、抽象数据类型的定义由三元组来定义：(D,S,P)其中，D是数据对象， S是D上的关系集，P是对D的基本操作集。 9、写出抽象数据类型线性表的定义 ADT List{ 数据对象：D={ai | ai ∈Elemset, i=1,2,…,n,n≥0} 数据关系：R={< ai-1 , ai> | ai-1 , ai ∈D, i=2,…,n} 基本操作： InitList(&L) //构造一个空的线性表L DestroyList(&L) //消毁线性表L ListLength(L) //返回L中数据元素的个数 ListInsert(&L,i,e) // 1 ≤ i ≤ ListLength(L)+1,在L中第i个位置之前插入数据元素e,L长度加1 ListDelete(&L,i,&e) // 1 ≤ i ≤ ListLength(L),删除L中的第i个元素，并用e 返回 ListTraverse(L,visit()) //依次对L的每个元素调用函数visit() ………… } ADT List 10、指出线性表顺序存储、链式存储结构的优缺点。 答：顺序存储优点：逻辑上相邻，物理位置也相邻，可以随机存取表中任一元素；缺点：插入和删除元素时需要移动大量元素。 链式存储结构优点：插入、删除元素时不需要移动元素；缺点：逻辑上相邻，物理位置不一定相邻，不能随机存取表中元素，需要依次查找，求线性表的长度时不如顺序存储结构方便，需要逐个结点搜索计算，或设置带头结点的线性链表。 11、完成下列在单链表中删除元素算法 Status ListDelete_L(LinkList &L, int i, ElemType &e){ //删除第i个元素e p = L; j =0; //p指向头结点 while(p->next && j 数据结构09 一. 填空题（26分，每空2分） 1. 声明抽象数据类型的目的是________________________________________。 2. 已知结点类Node 单选题(每题2分，共20分) 1. 1. 对一个算法的评价，不包括如下(B )方面的内容。 A .健壮性和可读性 B .并行性 C .正确性 D .时空复杂度 2.2. 在带有头结点的单链表HL 中，要向表头插入一个由指针 p 指向 的结点，则执行(A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; 都具有相同的(A )。 A.行号 B .列号 C .元素值 D .非零元素个数 9. 快速排序在最坏情况下的时间复杂度为(D )。 A. O(log 2n) B . O(nlog 2n) C . 0(n) D 10.10. 从二叉搜索树中查找一个元素时，其时间复杂度大致 为 A. O(n) B. O(1) C. O(log 2 n) D. O(n 二、 运算题(每题6分，共24分) 1. 1. 数据结构是指数据及其相互之间的 _________________ 。当结点之 间存在M 对N (M N)的联系时，称这种结构为 __________________________ 。 2. 2. 队列的插入操作是在队列的_ _尾 ________ 行，删除操作是在队 列的 ____ 首 _____ 行。 3. 3. 当用长度为N 的数组顺序存储一个栈时，假定用top==N 表示栈 C. p->next=HL; p=HL; 3. 3. A. C. D. HL=p; p-> next=HL; 对线性表，在下列哪种情况下应当采用链表表示? 经常需要随机地存取元素 B. 表中元素需要占据一片连续的存储空间 一个栈的输入序列为1 2 3， 4. 4. 列的是(C ) A. 2 3 1 C. 3 1 2 AOV 网 是一种(D ) 有向 图 B .无向图 (B ) 经常需要进行插入和删除操作 D.表中元素的个数不变 则下列序列中不可能是栈的输出序 B. 3 2 1 5. 5. 6. .无向无环图 D .有向无环图 采用 开放定址法处理散列表的冲突时，其平均查找长度( B. 高于链接法处理冲突 D .高于二分查找 7. 8. 6. A.低于链接法处理冲突 .与链接法处理冲突相同 7. 参数。 A.值 8. B)。 若需要利用形参直接访问实参时，应将形参变量说明为( B .函数 C .指针 D .引用 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点 9. .0(n 2) (C )。 2 ) 南京工程学院试卷（题）库建设与管理办法 （修订） 为了进一步深化教学改革，加强课程建设，提高教学质量，完善学分制学籍管理条例，实行“教考分离”，规范我校试卷（题）库的建设和管理，使考试结果能客观、公正、全面地衡量学校的教学质量和学生的学习效果，特制定本办法。 第一条指导思想 从培养高质量应用型人才出发，以考查学生能力、素质为目的，通过考试正确引导学生认真、全面地学习课程内容，系统地掌握基本理论、基础知识、基本技能，培养和提高学生分析问题、解决问题的能力，树立良好的学风。 第二条原则和范围 1．建立试卷（题）库的课程主要放在对提高学校教学质量和实现人才培养目标作用大、影响广及学时数较多的基础课和主干专业基础课，以及部分有条件建试卷（题）库的其它课程，由教务处和各院（系、部、中心）进行统一规划，分年度分步实施。 2.试卷（题）库的建设分为学校自建和外购两种形式。学校自建以试卷库为主；对市场上比较成熟且符合我校办学特色的基础课和专业基础课试题库，经调研论证及教务处批准可以申请购买。 第三条组织落实 1. 试卷库建设由教务处负责，各院（系、部、中心）分别成立试卷库建设领导小组，由分管教学的领导任组长，负责本部门有关课程试卷库的建设和规划工作。各试卷库建设领导小组下设试卷库建设课程小组，小组成员由该课程的任课教师及部分同专业的其他教师组成，负责本课程试卷库的建设工作。 2. 试卷库建设实行立项管理，由试卷库建设课程小组负责人填写《南京工程学院试卷库建设立项申请表》（见附件1），经审批后开始建设。 3.试卷库建设完成后，教务处将组织有关专家进行论证（论证表见附件2），符合要求后方可投入使用。 第四条命题要求 1．覆盖要全面 命题要以教学大纲为依据，范围要覆盖课程的基本章节，引导学生全面掌握课程的教学内容和知识。组配试卷时要避免同一问题在同一试卷的不同类型题中重复出现。 每门课程都有最基本的、相对重要的、要求学生必须掌握的内容，在命题时应突出这些内容，通过较多的题量和较高的分值来体现。 2．难度要适中 在严格按教学大纲命题的原则下，题目的深浅、难易要符合大多数学生的实际。每套试卷中有60%左右为基本题，30%左右为提高、综合题，10%左右为较高难度和深度的试题。每套试卷的总分为100分，总体难度以中等程度的学生得75分左右为宜，考试成绩统计结果应近似正态分布。每门课程要根据课程特点确定相应客观题型与主观题型及不同难易程度题目的比例，试题要能够体现出学生的学习水平高低。 3．题型要丰富 每份试卷的题型应安排合理，可采用填空题、选择题（单项或多项）、判断题（是非题）等客观性题型和问答题、分析题、论述题、实验技能题、计算题、证明题等主观性题型。也可根据各门课程的特点，选择其它较适合的题型。必要时，应对题型给出明确的说明或指导语。 4．题量要适度 每套试卷应根据课程性质保证有恰当的题量，一般按120分钟考试时间设计试卷，题量以学习能力较好的学生在90分钟内可以完成，多数学生能在规定时间内完成为宜。每门课程试卷库中的每套试卷难易度、题量、题型、结构应基本相当。 5．附件要齐全 试题应有参考答案、评分标准和评分细则，属问答题、论述题、分析题等类型的试题可以不写出详细答案，但要列出答案要点及评分标准；属计算、证明题的，如要求按步骤给分的，应列出分步评分标准。 6．用字要规范 注意事项： 1、下面关于串的叙述中，哪一个是不正确的？（ ） A ．串是字符的有限序列 B ．空串是由空格构成的串 C ．模式匹配是串的一种重要运算 D ．串既可以采用顺序存储，也可以采用链式存储 2、设无向图的顶点个数为n ，则该图最多有（ ）条边。 A ．n-1 B ．n(n-1)/2 C ． n(n+1)/2 D ．0 3、以下数据结构中，（ ）是非线性数据结构。 A ．树 B ．字符串 C ．队列 D ．栈 4、下面关于线性表的叙述中，错误的是哪一个？（ ） A ．线性表采用顺序存储，必须占用一片连续的存储单元。 B ．线性表采用顺序存储，便于进行插入和删除操作。 C ．线性表采用链接存储，不必占用一片连续的存储单元。 D ．线性表采用链接存储，便于插入和删除操作。 5、假设以数组A[m]存放循环队列的元素,其头尾指针分别为front 和rear ，则当前队列中的元素个数为（ ）。 A ．(rear-front+m)%m B ．rear-front+1 C ．(front-rear+m)%m D ．(rear-front)%m 6、在单链表指针为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; 7、设栈的输入序列是1，2，3，4,则（ ）不可能是其出栈序列。 A ．1，2，4，3 B ．2，1，3，4 C ．1，4，3，2 D ．4，3，1，2， 8、广义表（a,(b,c),d,e ）的表头和表尾分别为（ ）。 A ．a 和(b,c),d,e B ．（a ）和(b,c),d,e C ．a 和 ((b,c)，d,e) D ．(a) 和((b,c)，d,e) 9、栈和队都是（ ） A ．顺序存储的线性结构 B ．链式存储的非线性结构 C ．限制存取点的线性结构 D ．限制存取点的非线性结构 10、从逻辑上可以把数据结构分为（ ）两大类。 A ．动态结构、静态结构 B ．顺序结构、链式结构 C ．线性结构、非线性结构 D ．初等结构、构造型结构 11、下列四个序列中，哪一个是堆（ ）。 A ．75,65,30,15,25,45,20,10 B ．75,65,45,10,30,25,20,15 C ．75,45,65,30,15,25,20,10 D ．75,45,65,10,25,30,20,15 12、在下述结论中，正确的是（ ） ①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换; ④深度为K 的完全二叉树结点个数小于或等于深度相同的满二叉树。 A ．①②③ B ．②③④ C ．②④ D ．①④ 13、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ） A ．9 B ．11 C ．15 D ．不确定 14、设森林F 中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。 与森林F 对应的二叉树根结点的右子树上的结点个数是（ ）。 A ．M1 B ．M1+M2 C ．M3 D ．M2+M3 15、在下面的程序段中，对x 的赋值语句的频度为（ ）。 FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A ． O(2n) B ．O(n) C ．O(n 2) D ．O(log2n) 16、一个n 个顶点的连通无向图，其边的个数至少为（ ）。 A ．n-1 B ．n C ．n+1 D ．nlogn ； 17、二叉树的第I 层上最多含有结点数为（ ） A ．2I B ． 2I-1-1 C ． 2I-1 D ．2I -1 18、下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。 A ．选择 B ．冒泡 C ．归并 D ．堆 19、二维数组A 的元素都是6个字符组成的串，行下标i 的范围从0到8，列下标j 的范围从1到10。若A 按行存放，元素A[8，5]的起始地址与A 按列存放时的元素（ ）的起始地址一致。 A ．A[8,5] B ． A[3,10] C ． A[5,8] D ． A[0,9] 20、散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的关系，则选择好的（ ）方法是散列文件的关键。 A ．散列函数 B ．除余法中的质数 C ．冲突处理 D ．散列函数和冲突处理 期末考试《数据结构》A 卷 一、单项选择题（请将正确答案的字母填写在每题对应的括号内，每小题1分，共20分） 姓名:________ 学号:__________ 年级:______________ 专业:_____________ …….……………………….密…………………封…………………线………………………… 《数据结构》试题参考答案 （开卷） （电信系本科2001级 2002年12月） 一、回答下列问题 (每题4分，共36分) 1. 某完全二叉树共有15381个结点，请问其树叶有多少个？ 答：n2=?n/2?=?15381/2?=7691(个) 2. 假设有二维数组A 7×9，每个元素用相邻的6个字节存储，存储器按字节编址。已知A 的起始存储位置（基地址）为1000，末尾元素A[6][8]的第一个字节地址为多少？若按列存储时，元素A[4][7]的第一个字节地址为多少？ 答：① 末尾元素A[6][8]的第一个字节地址＝1000＋（7行×9列—1）×6B ＝1000＋62×6=1372 ②按列存储时，元素A[4][7]的第一个字节地址＝1000＋（7列×7行＋4）×6B ＝1000＋53×6=1318 3. 在KMP 算法中，已知模式串为ADABBADADA ，请写出模式串的next[j]函数值。 答：根据 0 当j ＝1时 next[ j ]＝ max { k |1 一、单项选择题 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; 南京工程学院试卷题库建设与管理规定 TTA standardization office【TTA 5AB- TTAK 08- TTA 2C】 南京工程学院试卷（题）库建设与管理办法 （修订） 为了进一步深化教学改革，加强课程建设，提高教学质量，完善学分制学籍管理条例，实行“教考分离”，规范我校试卷（题）库的建设和管理，使考试结果能客观、公正、全面地衡量学校的教学质量和学生的学习效果，特制定本办法。 第一条指导思想 从培养高质量应用型人才出发，以考查学生能力、素质为目的，通过考试正确引导学生认真、全面地学习课程内容，系统地掌握基本理论、基础知识、基本技能，培养和提高学生分析问题、解决问题的能力，树立良好的学风。 第二条原则和范围 1．建立试卷（题）库的课程主要放在对提高学校教学质量和实现人才培养目标作用大、影响广及学时数较多的基础课和主干专业基础课，以及部分有条件建试卷（题）库的其它课程，由教务处和各院（系、部、中心）进行统一规划，分年度分步实施。 2.试卷（题）库的建设分为学校自建和外购两种形式。学校自建以试卷库为主；对市场上比较成熟且符合我校办学特色的基础课和专业基础课试题库，经调研论证及教务处批准可以申请购买。 第三条组织落实 1. 试卷库建设由教务处负责，各院（系、部、中心）分别成立试卷库建设领导小组，由分管教学的领导任组长，负责本部门有关课程试卷库的建设和规划工作。各试卷库建设领导小组下设试卷库建设课程小组，小组成员由该课程的任课教师及部分同专业的其他教师组成，负责本课程试卷库的建设工作。 2. 试卷库建设实行立项管理，由试卷库建设课程小组负责人填写《南京工程学院试卷库建设立项申请表》（见附件1），经审批后开始建设。南京工程学院071电力系统通信网试卷A
数据结构试卷-A+答案
算法与数据结构试题及答案
《数据结构》题库及答案
南京工程学院C语言试卷3
数据结构试卷及答案90325
南京工程学院数据结构样卷09级加答案
数据结构试题及答案(10套最新)
南京工程学院试卷(题)库建设与管理办法.doc
数据结构试卷及答案
数据结构试卷和答案
算法与数据结构题库与答案
南京工程学院试卷题库建设与管理规定
相关主题
文本预览