德州有做网站的,本地wordpress打开慢,营销型网站建设 价格,兰州做网站公司es5188第1章 绪论
单选题 数据在计算机的存储器中表示时#xff0c;逻辑上相邻的两个元素对应的物理地址也是相邻的#xff0c;这种存储结构称之为________。 B. 顺序存储结构 算法指的是________。 D. 求解特定问题的指令有限序列 下面程序段的时间复杂度为#xff1a;_______…第1章 绪论
单选题 数据在计算机的存储器中表示时逻辑上相邻的两个元素对应的物理地址也是相邻的这种存储结构称之为________。 B. 顺序存储结构 算法指的是________。 D. 求解特定问题的指令有限序列 下面程序段的时间复杂度为________。 fori1ini
forj1jnj
sa[i][j]; D. O(n²) 设数据结构SDR其中D{1234}R{1223❤️4}则数据结构S属于________。 B. 线性结构 设部门的上级领导下级的数据结构SDR其中D{abcde}R{ a领导b a领导cb领导d b领导 e }则数据结构S属于________。 C. 树结构 以下数据结构中________是线性结构。 A. 字符串 在数据结构中从逻辑上可以把数据结构分为________。 C. 线性结构和非线性结构 某算法的语句执行频度为n²nlog₂n3n8其时间复杂度为________。 C. O(n²) 算法的时间复杂度取决于________。 D. A和B 设数据结构SDR其中D{1234}R{12233441}则数据结构S是 。 C. 图结构 算法分析的两个主要方面是 。 B. 时间复杂度和空间复杂度 抽象数据类型的三个组成部分分别是 。 C. 数据对象、数据关系、基本操作 以下程序段中语句“m;”的语句频度是 。 int m0;
for(i1;in;i)
for(j1;j2*i;j)m;A. n(n1) 链式存储的存储结构所占存储空间 。 A. 分为两部分一部分存放结点值另一部分存放表示结点间关系的指针
填空题
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。线性结构中元素之间存在一对一关系树结构中元素之间存在一对多关系图结构中元素之间存在多对多关系。链式存储结构为了表示结点之间的关系通常需要给每个结点附加指针字段用于存放后继元素的地址。抽象数据类型一般指由用户定义的、表示应用问题的数学模型以及定义在这个模型上的一组操作的总称。具体包括3个部分数据对象、数据关系、基本操作。算法的5个特征是有穷性、确定性、可行性、输入、输出。顺序存储结构中数据元素之间的逻辑关系是由物理地址表示的链式存储结构中数据元素之间的逻辑关系是由指针表示的。
简答题 简述逻辑结构的四种基本关系并画出它们的关系图。 逻辑结构的四种基本关系集合结构、线性结构、树形结构、图形结构。 集合结构元素之间无特定关系线性结构元素之间存在一对一的关系树形结构元素之间存在一对多的层次关系图形结构元素之间存在多对多的关系 存储结构有哪两种基本的存储方法实现 顺序存储链式存储 简述算法的定义与特性。 算法是解决问题的一系列步骤或程序。特性包括有穷性、确定性、可行性、输入、输出。
第2章 线性表
单选题 以下叙述正确的是 。 B. 顺序表可以实现随机存取。 线性表a1a2…an以链式方式存储时访问第i个位置上的元素的时间复杂度为 。 B. O(n) 线性表的顺序存储结构是一种 的存储结构。 A. 随机存取 线性表在 情况下适用于使用链式结构存储。 B. 需要不断对线性表进行插入、删除操作。 以下属于顺序表的优点的是 。 C. 存储密度大。 下列叙述错误的是 。 D. 线性表的链式存储结构优于顺序存储结构。
填空题
顺序表中逻辑上相邻的元素物理位置一定相邻单链表中逻辑上相邻的元素物理位置不一定相邻。若一个长度为n的顺序表中在第i个位置1≤i≤n插入一个新的元素共需要移动n-i个元素若一个长度为n的顺序表中删除第i个元素1≤i≤n时需向前移动n-i-1个元素。已知顺序表中第一个元素的存储地址是1000每个元素的长度为4则第7个元素的存储地址是1024。向一个有200个元素的顺序表中插入一个新元素并保持原来顺序不变平均要移动的元素个数为100。在一个以L为头指针的单循环链表中p指针指向链尾的条件是p-next L。
判断题 线性表中每个元素都有一个前驱和一个后继。 错 线性表中所有元素的数据类型必须相同。 对 顺序表结构适宜于进行随机存取而链表适宜于进行顺序存取。 对 单链表可以实现随机存取。 错 线性表若采用链式存储结构时其存储结点的地址可以连续也可以不连续。 对 线性表的顺序存储结构优于链式存储结构。 错 进行插入删除操作时在链表中比在顺序表中效率高。 对 在顺序表中逻辑上相邻的元素物理位置上不一定相邻。 错 若频繁地对线性表进行插入和删除操作该线性表采用链式存储结构更合适。 对
简答题 简述线性结构的特点。 线性结构的特点是元素之间存在一对一的线性关系每个元素只有一个前驱和一个后继。 简述顺序表和链表的主要优缺点。 顺序表优点支持随机存取存储密度大。缺点插入和删除操作效率低存储空间不灵活。链表优点插入和删除操作效率高存储空间灵活。缺点不支持随机存取存储密度低。
综合题 请用代码描述如下单链表的插入操作将s所指结点插入到结点a和b之间。 s-next a-next;
a-next s;请用代码描述如下单链表的删除操作将结点b删除。 a-next b-next;
delete b;3.**请用代码描述 ba-next x-prea a-nextx x-nextb b-prex 4. 删除p的所指节点b ba-next ca-next-next a-nextc c-prea delete b 第3章 栈和队列
一、单选题
栈在( D,递归表达式求值括号匹配 )中有所应用。栈和队列的共同点是( C. 只允许在端点处插入和删除元素 )。最大容量为n的循环队列队尾指针是rear队头是front则判断队空和队满的条件正确的是( B. 队空rearfront队满(rear1)%nfront )。下列说法中符合队列性质的是( D. 只能在一边插入和另一边删除 )。设一个队列的入队序列为d,c,b,a则队列的输出序列是( B.dcba)。若用一个大小为6的数组实现循环队列且当前rear和front的值分别为0和3当从队列中删除一个元素再插入两个元素后rear和front的值分别为( C. 2和4 )。为解决计算机主机与打印机间速度不匹配问题通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是( A. 队列 )。若一个栈以数组V[1…n]存储初始栈顶指针top设为n1则元素x进栈的正确操作是( C top–;V[top]x; )。若一个栈以数组V[1…n]存储初始栈顶指针top设为0则元素x进栈的正确操作是( A. top; V[top]x; )。若已知一个栈的入栈序列是123…n其输出序列为p1p2p3…pn若p1n则pi为( C. n-i )。设计一个判别表达式中左、右括号是否配对出现的算法采用( C. 栈 )数据结构最佳。一个栈的入栈序列是a,b,c,d,e, 且在入栈过程中可出栈则栈的不可能的输出序列是( C. dceab )。队列是限定在 C.队尾处进行插入操作的线性表。设栈S和队列Q的初始状态为空元素e1,e2,e3,e4,e5,e6依次进入栈S一个元素出栈后即进入Q若6个元素出队的序列是e2,e4,e3,e6,e5,e1则栈S的容量至少应该是 B3 。若元素a,b,c,d,e,f依次进栈允许进栈、出栈操作交替进行但不允许连续三次进行出栈工作则不可能得到的出栈序列是 D.afedcb 。
二、判断题
队列是一种插入与删除操作分别在表的两端进行的线性表是一种先进后出的线性结构。 × 循环队列属于队列的链式存储结构。 × (是队列的顺序存储结构)若输入序列为1,2,3,4,5,6则通过一个栈可以输出序列3,1,5,6,4,2。 × 一个递归算法必须包括终止条件和递归部分。 √
三、简答题 栈是一种先进后出LIFO的线性数据结构只允许在表的一端进行插入和删除操作即栈顶端。栈的特点是后进入的元素先出来它可以通过顺序存储结构或链式存储结构实现。常见的应用包括递归调用、表达式求值、括号匹配等。
队列是一种先进先出FIFO的线性数据结构插入操作在队尾进行删除操作在队头进行只能在表的两端进行操作。队列的特点是先进入的元素先出来它同样可以通过顺序存储结构或链式存储结构实现。常见的应用包括任务调度、缓冲区管理等。
四、算法分析题 1、
Status Push(SqStack S, SElemType e)
{ if (S.top MAXSIZE - 1) return ERROR; // 判断栈满的条件S.data[S.top] e; // 将e入栈栈顶指针top上移return OK;
} 2、
Status Pop(SqStack S, SElemType e)
{ if(S.top -1) return ERROR; // 判断栈空的条件e S.data[S.top--]; // 用e返回栈顶元素栈顶指针top下移return OK;
} 3、
void conversion(int N)
{ InitStack(S);while(N){ Push(S, N % 2); // ①将N % 2入栈N N / 2;}while(!StackEmpty(S)){ Pop(S, e); // ②从栈中出栈得到二进制数的每一位cout e;}
}4、
Status EnQueue(SqQueue Q, QElemType e)
{ if((rear1)%nfront)return ERROR;Q[rear]e;rear;Return OK
}Status DeQueue(SqQueue Q, QElemType e)
{ if(rearfront)return ERROR;eQ[front];front;Return OK
}第4章 串、数组和广义表
一、单选题
下面说法不正确的是C. 广义表的表头总是一个广义表。两个串相等必有串长度相等且B. 串中各位置字符均对应相等。设有两个串p和q求q在p中首次出现的位置的运算称作B. 模式匹配。已知串S“abcaba”的next数组为C. 011123)。 解析 1. abcaba --000121 (就是比较每个字符和首部是否相等) 2.000121 每个加1------ 111232 3.111232 向右移为011123 4.得到结果011123下面表述正确的是A. 串是一种特殊的线性表。对于n阶对称矩阵如果采用压缩存储需要D. n2/2个存储单元。对特殊矩阵进行压缩存储目的是C. 节省存储空间。设一维数组中有n个元素则读取第i个数组元素的平均时间复杂度为C. O(1)。数组A[0…7,0…9]的每个元素占3个字节将其按行列先次序存储在起始地址为1000的内存单元中则元素A[74]的起始地址是D. 1222。数组A[0…5,0…6]的每个元素占五个字节将其按行优先次序存储在起始地址为1000的内存单元中则元素A[55]的地址是B. 1200。假设二维数组A[1…60,1…70]以列序为主序顺序存储其基地址是10000每个元素占2个存储单元则元素A[32,58]的存储地址是B. 16902。设广义表La,b,c则L的长度和深度分别为C 1和2。 解析长度为第一层的所有元素个数1深度为一共几层括号2对广义表L((a,b),(c,d),(e,f))执行操作GetTail(GetTail(L))的结果是B.((e,f))。
二、填空题
若矩阵中的所有元素均满足aijaji则称此矩阵为 对称矩阵。数组A[0…7,0…8]的每个元素占4个字节分别将其按行优先、列优先次序存储在起始地址为1000的内存单元中则元素A[3,6]的地址是1132 和1204。模式串P“abaabcac”的next函数值序列为 011223012。设字符串S‘You︺did︺a︺very︺good︺job!’其长度是24。子串“ture”在主串“datastructure”中的位置 9。设串S“abcde”其长度是 5。已知广义表L((a,b),(c,d))则head(L)是 (a,b) tail(L)是 ((c,d)) 长度为 2 深度为 2。广义表a,b,c,d的表头是 (a,b,c,d) 表尾是 () 。已知广义表C (a,(b,A),B)则其长度是 3 深度是 无穷大 。利用KMP算法进行模式匹配时模式串t“abcabaa”的next函数值是 0111232。
三、判断题
串是一种数据对象和操作都特殊的线性表。(√)KMP算法的特点是在模式匹配时指示主串的指针不会变小。(√)数组可看成线性结构的一种推广因此与线性表一样可以对它进行插入删除等操作。×数组和广义表不属于线性结构。(×)二维数组A[-3…5,0…10]中共有80个元素。×稀疏矩阵和特殊矩阵压缩存储后均可以实现随机存取。×数组元素的下标值越大存取时间越长。×子串在主串中的位置以子串的第一个字符在主串中的位置来表示。(√)KMP算法可以在O(mn)的时间数量级上完成串的模式匹配操作。√对n阶矩阵若矩阵中的元素在ij时均满足aij为0或为常数则称此矩阵为下三角矩阵。√一个广义表的表头总是一个广义表。×
四、简答题 串的模式匹配是指在一个主串中查找某个子串的过程。常用的两种模式匹配算法是暴力匹配算法BF算法和Knuth-Morris-Pratt算法KMP算法。
五、算法分析题 1、BF算法
int Index_BF(SString S, SString T, int pos) {int i pos;int j 1;while (i S.length j T.length) { // ① 两个串均未比较到串尾if (S.ch[i] T.ch[j]) { // ② 继续比较后续字符
cppi;j;} else {i i - j 2; // ④ 指针回溯重新开始匹配j 1;}}if (j T.length) // ⑤ 匹配成功返回位置序号return i - T.length;elsereturn 0; // ⑥ 匹配失败返回0
}2、KMP算法
int Index_KMP(SString S, SString T, int pos) {int i pos;int j 1;while (i S.length j T.length) { // ① 两个串均未比较到串尾if (j 0 || S.ch[i] T.ch[j]) { // ② 继续比较后续字符i;j;} else {j T.next[j]; // ④ 子串向右滑动至第next[j]个位置}}if (j T.length) // ⑤ 匹配成功返回位置序号return i - T.length;elsereturn 0; // ⑥ 匹配失败返回0
}一、单选题
B. 100 解析哈夫曼树只有度每个节点孩子数为2和0的节点以满二叉树为例叶子节点有2(n)个总结点数有2(n1)-1个 得出总结点 n叶子结点数有(n1)/2 叶子结点 n总结点数有2n-1 2.B. 010011 解析前缀码是指画出的图形中不存在节点之间为父子关系D. 501D. 2^h-1B 11 解析n0n21记住就行D5B. 只有一个结点的二叉树的度为0D. 2i - 1A. 11B. 10
二、填空题
66316DGEBFCA74, 96 7.FBADCFHGIJKn17 (2^(5-1)16,第五层本来有16个结点但是有16-718没有子节点所以有78/211个叶子结点)是
三、判断题
是是是错误错误错误错误错误错误错误是错误
四、综合题
先序遍历ABCDEFGHIJKL, 中序遍历DCEBFAIHGKLJ, 后序遍历DECFBIHKLJGA先序遍历ABDHEIJCFLGMN, 中序遍历HDBIEJAFCLMGN, 后序遍历HDIJEBLFMNFCA先序遍历ABCDEFGH, 中序遍历DCEBAFHG, 后序遍历ECBGHFA先序遍历ABCDEF, 中序遍历CBDAFE, 后序遍历CDBFEA哈夫曼编码A: 01, B: 10, C: 000, D: 001, E: 11 WPL 91数据传输长度最短的编码C: 000,S:001,E:01,A:10,T:11 STATE:00111101101 SEAT:001011011 ACT:1000011 TEA:110110 CAT:0001011 SET:0010111 A:10 EAT:011011先根遍历ABDEIJFGKHC, 后根遍历BIJEFKGHDC
一、单选题
D. n(n-1)/2 解析最多所以是每个结点都和其余n-1个结点相连有n*(n-1)个边 无向图为n*(n-1) /2 因为重复边要除以2 有向图为n*(n-1) 没有重复边B. n(n-1)B. 拓扑排序B. 每个顶点的度等于其入度与出度之和A. 2 解析一个边连接两个顶点所以是边*2B. 1 解析入度之和出度之和A. 从源点到汇点的最长路径B. 任何一个关键活动提前完成整个工程也将提前完成B 12A. n-1 解析树的顶点数 边数1随便画个树就能看出来 11.B. 3,1,2,4,5 解析每次找入度为0的顶点输出然后删除这个顶点和连接这个顶点的边继续找入度为0的D. 对称矩阵
二、填空题
620
三、判断题
错误错误错误是是是是
四、综合题 1.
DFS序列1364527BFS序列1346527
[图示 Prim 算法和 Kruskal 算法构造最小生成树的全过程][AOV-网的拓扑排序序列] 一种拓扑排序序列ACEBDFHGI另一种拓扑排序序列ACEHBDGFI Ve 和 Vl 表格如下
顶点最早发生时间 Ve最晚发生时间 Vl1002333454101058961414
关键路径为1 -a1-2-a3-4-a8-6工程完工的最短时间为 14 天
解析最早发生时间就是从起点到终点找所有连接和中最大的 最晚发生时间就是从终点到起点找结点数-边值差值最小的 vl - ve 0 的活动为关键活动关键活动跟状态连起来就为关键路径。
第7章 查找
一、单选题 对n个元素的表做顺序查找时若查找每个元素的概率相同则平均查找长度为 。 C. (n1)/2 适用于折半查找的表的存储方式及元素排列要求为 。 D. 顺序方式存储元素有序 折半查找有序表4610122030507088100。若查找表中元素58则它将依次与表中 比较大小查找结果是失败。 A. 20 70 30 50 对22个记录的有序表作折半查找当查找失败时至多需要比较 次关键字。 C. 5 分别以下列序列构造二叉排序树与用其它三个序列所构造的结果不同的是 。 C (100,60,80,90,120,110,130) 解析二叉排序树则为左边比父类小右边比父类大每次从根节点开始找 设哈希表长为14哈希函数是H(key)key%11表中已有数据的关键字为15386184共四个现要将关键字为49的元素加到表中用二次探测法解决冲突则放入的位置是 。 D. 9 解析二次探测法为二次幂12,22,32,42,累加 线性探测为1 2 3 4 5 6线性累加 衡量查找算法效率的主要标准是 。 C. 平均查找长度
二、填空题
计算哈希地址时若产生冲突可以采用开放定址法和链地址法解决冲突。在长度为500的有序表中进行折半查找查找不成功时和给定值进行比较的关键字个数最多为9。 解析log以2为底500的对数9
三、综合题 已知如下11个数据元素的有序表0513192137566475808892请画出其“折半查找”到数据“37”的全过程。 第一步中间位置为56与37比较3756继续在左半部分查找。第二步中间位置为19与37比较3719继续在右半部分查找。第三步中间位置为37查找成功。 已知一组关键字为477291116922283散列函数为H(key)key%11用线性探测法处理冲突。设表长为11试构造这组关键字的散列表并写出查找每个关键字的比较次数最后计算查找成功时的平均查找长度四舍五入保留一位小数。
散列地址012345678910关键字112247921637298比较次数121114122
计算查找成功时的平均查找长度 15/91.7
第8章 排序
一、单选题
1、从未排序序列中依次取出元素与已排序序列中的元素进行比较将其放入已排序序列的正确位置上的方法这种排序方法称为 。 C插入排序
2、从未排序序列中挑选元素并将其依次放入已排序序列初始时为空的一端的方法称为 。 D选择排序
3、对n个不同的关键字由小到大进行冒泡排序在下列 情况下比较的次数最多。 B从大到小排列好的
4、对n个不同的排序码进行冒泡排序在元素无序的情况下比较的次数最多为 。 Dn(n-1)/2
5、下面 方法是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。 D基数排序
6、若一组记录的排序码为46, 7956384084则利用快速排序的方法以第一个记录为基准得到的一次划分结果为 。 A. 38 40 46 56 79 84
7、下列关键字序列中 是堆。 D162353319472
8、堆排序是一种 排序。 B选择
9、堆的形状是一棵 。 C完全二叉树
10、下列排序算法中 不属于选择排序。 A希尔排序
11、下列排序算法中不稳定的是 。 D快速排序
二、综合题
设待排序的关键字序列为{1221630281016*20618}试分别写出使用以下排序方法每趟排序结束后关键字序列的状态。
①直接插入排序
[2 12] 16 30 28 10 16* 20 6 18
[2 12 16] 30 28 10 16* 20 6 18
[2 12 16 30] 28 10 16* 20 6 18
[2 12 16 28 30] 10 16* 20 6 18
[2 10 12 16 28 30] 16* 20 6 18
[2 10 12 16 16* 28 30] 20 6 18
[2 10 12 16 16* 20 28 30] 6 18
[2 6 10 12 16 16* 20 28 30] 18
[2 6 10 12 16 16* 18 20 28 30]
②希尔排序
10 2 16 6 18 12 16* 20 30 28 增量选取5
6 2 12 10 18 16 16* 20 30 28 增量选取3
2 6 10 12 16 16* 18 20 28 30 增量选取1
③简单选择排序 [2],12,16,6,30… [2,6],12,16,30,29 [2,6,10,]… [2,6,10,12],… [2 6 10 12 16 16* 18 20 28 30]
一直取最小/最大 和后面的交换位置
④ 冒泡排序
2 12 16 28 10 16* 20 6 18 [30]
2 12 16 10 16* 20 6 18 [28 30]
2 12 10 16 16* 6 18 [20 28 30]
2 10 12 16 6 16* [18 20 28 30]
2 10 12 6 16 [16* 18 20 28 30]
2 10 6 12 [16 16* 18 20 28 30]
2 6 10 [12 16 16* 18 20 28 30]
2 6 10 12 16 16* 18 20 28 30]
⑤快速排序
12 [6 2 10] 12 [28 30 16* 20 16 18]
6 [2] 6 [10] 12 [28 30 16* 20 16 18 ]
28 2 6 10 12 [18 16 16* 20 ] 28 [30 ]
18 2 6 10 12 [16* 16] 18 [20] 28 30
16* 2 6 10 12 16* [16] 18 20 28 30
