第一章 1.计算机由五部分构成：输入、运算器、存储器、控制器、输出 2.计算机三个子系统：处理器子系统、存储器子系统、输入输出子系统 3.输入输出通常被称为人机交互 4.哈佛结构将数据和程序分开存放 5。程序存储原理：程序被要求在执行前存放在存储器中，还要求程序和数据采用同样的存储格式 6.计算机系统是由计算机硬件和软件组成的 ①计算机硬件系统包括：处理器系统（主机）、存储器系统、外部设备（输入设备、输出设备） ②计算机软件系统包括：A.系统软件（操作系统、编程语言/计算机语言系统、工具软件）、 B.应用软件 7.计算机硬件史 ①第一代计算机：电子管 ②第二代计算机：晶体管 ③第三代计算机：集成电路（IC） ④第四代计算机（微型计算机、个人计算机）：大规模集成电路 8.计算机的类型 ①巨型计算机（超级计算机） ②大型计算机 ③小型计算机 ④微型计算机 9.硬件的三个子系统 计算机三个子系统：处理器子系统、存储器子系统、输入输出子系统 存储器子系统：存储数据、程序和参与运行程序 10.计算机软件 11.计算机如何运行 事实上，只要通电启动，机器就开始执行程序，直到关机为止 计算机通电后，CPU执行启动程序BIOS（基本输入/输出系统），其基本任务就是把存放在磁盘中的操作系统调入内存执行，此后将在操作系统的管理下直接操控计算机的硬件。12.信息系统 信息系统的基本功能是为需要者提供特定的信息，支持用户迅速、有效地输入、存储、处理和获取信息。 信息系统有以下6个要素： ①硬件 ②软件 ③数据/信息 ④用户 ⑤过程 ⑥通信 13.HTML:制作web的超文本置标语言 14.web浏览器为用户访问因特网提供了简单的方法，该系统基于超文本技术。 超文本（Hypertext）还包括视频、音频、动画、图片等其他数据。
模拟 2 得分一．选择题(本大题共15 题，每题 1 分，共15 分 ) 1．数据在计算机内存中的表示是指 A. 数据的存储结构 C. 数据的逻辑结构 。 B. 数据结构 D. 数据元素之间的关系 2. 对线性表，在下列情况下应当采用链表表示的是 A. 经常需要随机地存取元素 B. 经常需要进行插入和删除操作 C. 表中元素需要占据一片连续的存储空间 D. 表中的元素个数不变 。 3．与单链表相比，双链表的优点之一是 A．插入、删除操作更加简单。 。 B．可随机访问。 C．可以省略表头指针或表尾指针 D．访问前驱结点更加方便 4．如果最常用的操作是取第i 个结点及前驱，则采用 A．顺序表B．双链表 存储方式最节省时间。 C．单循环链表D．单链表 5．可以用带表头附加结点的链表表示线性表，也可以用不带表头附加结点的链表表示线性表，前者最主要的好处是。 A．可以加快对表的遍历 C．节省存储空间 6. 一个队列的入队序列是1,2,3,4, B. 使空表和非空表的处理统一 D. 可以提高存取表元素的速度则队列的输出序列是。 A. 4,3,2,1 B. 1,2,3,4 C. 1,4,3,2 D. 3,2,4,1 7．栈和队列的共同点是。 A．都是先进先出B．都是先进后出 C．属于非线性结构D．只允许在端点处插入和删除元素8．以下不是栈的基本运算的是。 A．删除栈顶元素C．判断栈是否为空B. 删除栈底元素D. 将栈置为空栈 9．一个递归的定义可以用递归过程求解，也可以用非递归过程求解，若从运行时间来看，通常__________ 。 A．非递归算法比递归算法快B．非递归算法比递归算法慢 10. C．非递归算法与递归算法时间一样D．非递归算法与递归算法时间不一定在一个非空二叉数的中序遍历序列中，根结点的右边。 A. 只有右子树上的所有结点 B.只有右子树上的部分结点 C. 只有左子树上的部分结点 D.只有左子树上的所有结点
浙江大学2007–2008学年秋季学期 《数据结构基础》课程期末考试试卷 开课学院：软件学院、计算机、竺可桢学院，考试形式：闭卷，允许带_ 无入场考试时间：_2007_年_11_月_17日, 所需时间： 120 分钟 考生姓名： ___学号：专业： ____教师：题序一二三四总分得分 评卷人 Answer Sheet Part I 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. Part II 1. c d e 2. c d 3. c d Part III 1. (a) (b) 1. (c)
2. (a) 2. (b) 3. 4. (a) 4. (b)
Part IV void Dijkstra( Table T )
NOTE: Please write your answers on the answer sheet. 注意：请将答案填写在答题纸上。 I. Please select the answer for the following problems. (20 points) (1)The time complexity of the following piece of code is (2 points) for(i=0; i
第三章习题 1. 按图3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答： ⑴如进站的车厢序列为123，则可能得到的出站车厢序列是什么？ ⑵如进站的车厢序列为123456，能否得到435612和135426的出站序列，并说明原因。（即 写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。 2. 设队列中有A、B、C、D、E这5个元素，其中队首元素为A。如果对这个 队列重复执行下列4步操作： （1）输出队首元素； （2）把队首元素值插入到队尾； （3）删除队首元素； （4）再次删除队首元素。 直到队列成为空队列为止，得到输出序列： （1） A、C、E、C、C （2） A、C、E （3） A、C、E、C、C、C （4） A、C、E、C 3. 给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈 空与栈满？
4. 按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，画出对 下列算术表达式求值时操作数栈和运算符栈的变化过程： A－B＊Ｃ／Ｄ＋Ｅ↑Ｆ 5. 试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形 如‘序列1& 序列2’模式的字符序列。其中序列1和序列2中都不含字符’&’，且序列2是序列1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘１+３&３－１’则不是。 6. 假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将 一个通常书写形式且书写正确的表达式转换为逆波兰式。 7. 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素 结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。 8. 要求循环队列不损失一个空间全部都能得到利用, 设置一个标志域tag , 以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。 9. 简述以下算法的功能（其中栈和队列的元素类型均为int）： （1）void proc_1(Stack S) { int i, n, A[255]; n=0; while(!EmptyStack(S))
第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）。【北京邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（）【中科院计算所1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 【南京理工大学1999 一、1（2分）【武汉交通科技大学1996 一、1（4分）】4．一个算法应该是（）。【中山大学1998 二、1（2分）】 A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C. 5. 下面关于算法说法错误的是（）【南京理工大学2000 一、1（1.5分）】 A．算法最终必须由计算机程序实现 B. 为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的
6. 下面说法错误的是（）【南京理工大学2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。【武汉交通科技大学1996 一、4（2分）】 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。【北方交通大学2000 二、1（2分）】 A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？【北方交通大学2001 一、1（2分）】 A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（）【北方交通大学2001 一、2（2分）】 A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学2001 一、10（3分）】
数据结构第三章习题 3．1 单项选择题 2.一个栈的入栈序列a, b, c, d, e, 则栈的不可能的输出序列是。 A. edcba B. Decba C. Dceab D. abcde 3. 若已知一个栈的入栈序列是1，2，3，………..n, 其输出序列为p1, p2, p3,……,pn, 若p1=n, 则pi为。 . B. n=I C. n- i+1 D.不确定4．栈结构通常采用的两种存储结构是。 A. 顺序存储结构和链表存储结构 B. 散链方式和索引方式 C.链表存储结构和数组 D. 线性存储结构和非线性存储结构5．判定一个栈ST（最多元素为m0）为空的条件是。 A. ST->top<>0 B. ST->top=0 >top<>m0 >top=m0 6．判定一个栈ST（最多元素为m0）为栈满的条件是。 A. ST->top!=0 >top==0 >top!=m0 >top==m0 7.栈的特点是，队列的特点是。 A先进先出 B. 先进后出 8. 一个队列的入栈序列是1，2，3，4，则队列的输出序列是。 A. 4,3,2,1 B. 1,2,3,4 C. 1,4,3,2 D. 3,2,4,1 9. 判定一个队列QU(最多元素为m0)为空的条件是。 >rear- QU->front==m0 >rear- QU->front-1==m0 >front== QU->rear D. QU->front== QU->rear+1
10.判定一个队列QU（最多元素为m0）为满队列的条件是。 >rear- QU->front==m0 >rear- QU->front-1==m0 >front== QU->rear >front== QU->rear+1 11. 判定一个循环队列QU(最多元素为m0)为空的条件是。 A. QU->front== （QU->rear+1）%m0 B. QU->front！= （QU->rear+1）%m0 >front== QU->rear >front！= QU->rear 12. 判定一个循环队列QU（最多元素为m0）为满队列的条件是。 A. QU->front== （QU->rear+1）%m0 B. QU->front！= （QU->rear+1）%m0 >front== QU->rear >front！= QU->rear+1 12. 向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行。 HS->next=s; A. s->next=HS->next; HS->next=s; B. s->next=HS; HS=s; C. s->next=HS; HS=HS->next; 13. 从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行。 A x=HS; HS=HS->next; B. x=HS->data; C. HS=HS->next; x=HS->data;
浙大数据结构与算法离线作业
————————————————————————————————作者：————————————————————————————————日期: ?
浙江大学远程教育学院 《数据结构与算法》课程离线作业 姓名:学号: 年级：2016春学习中心： ————————————————————————————— 一、填空题：(【序号,章，节】。。。。。。） 【１，１,2】线性结构中元素之间存在一对一关系，树形结构中元素之间存在 一对多关系,图形结构中元素之间存在多对多关系。 【2，１，2】为了最快地存取数据元素，物理结构宜采用顺序存储结构。 【３，1，2】存储结构可根据数据元素在机器中的位置是否一定连续分为顺序存储结构 , 链式存储结构。 【4，１，3】度量算法效率可通过时间复杂度来进行。 【5,1,３】设n 为正整数,下面程序段中前置以记号@的语句的频度是ｎ(n＋１)/2 。 fｏｒ(i=０; i } 【7,３,2】线性表（a1,a２，…，a n)有两种存储结构: 顺序存储结构和链式存储结构，请就这两种存储结构完成下列填充:顺序存储密度较大；顺序存储利用率较高;顺序可以随机存取；链式不可以随机存取；链式插入和删除操作比较方便。 【8,3,２】从一个长度为n的顺序表中删除第ｉ个元素(1≤i≤n)时，需向前移动n－ｉ个元素。 【９,3,2】带头结点的单链表Heaｄ为空的条件是Head-＞nexｔ=NUＬＬ。 【10,3，2】在一个单链表中ｐ所指结点（p所指不是最后结点)之后插入一个由指针s所指结点,应执行s->neｘt=_p-＞next;和p->next＝ｓ的操作。 【11，3,2】在一个单链表中删除p所指结点时，应执行以下操作： ｑ= p-＞ｎext； p->data= p->next-＞daｔａ； ｐ->ｎｅxｔ＝ p->next->ｎext ； frｅe(q); 【1２，3，2】带头结点的单循环链表Head的判空条件是Head-＞nexｔ==Head；不带头结点的单循环链表的判空条件是Heａd==NUＬL。 【13，3,2】已知L是带表头结点的非空单链表, 且P结点既然不首元结点,也不是尾元结点,试从下列提供的答案中选择合适的语句序列。 a．删除P结点的直接前驱结点的语句序列是１0 12 8 １1 4 14。 b. 删除结点P的语句序列是10 １2 7 ３ 1４。 c. 删除尾元结点的语句序列是９ 1１ 3 1４。 (１）P ＝P->nexｔ; （２） P－>ｎext ＝Ｐ; （3) P－>neｘt = Ｐ->next ->next; （４）Ｐ＝P->nｅxｔ -＞neｘt; (5) whiｌe (P ！= NULL）Ｐ＝ P->ｎext; (6) ｗhile (Q－>neｘt != NＵLL）{P = Q; Q ＝Ｑ－>ｎｅｘｔ}； (7） whｉｌe (P－>ｎｅxｔ！= Q) Ｐ＝ P－>nexｔ; (8)ｗhｉle （P-＞nexｔ->nｅxｔ！＝Q）P = P->ｎｅxｔ； (9) wｈｉlｅ（P－>nexｔ->neｘｔ != ＮULL) Ｐ = Ｐ－>next; (1０) Q = Ｐ; (１1）Ｑ= P->nｅxt; （１2）P ＝Ｌ; 浙江大学远程教育学院 《数据结构与算法》课程离线作业 一、填空题：（【序号，章，节】。。。。。。） 【1，1，2】线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 【2，1，2】为了最快地存取数据元素，物理结构宜采用序存储结构。3，1，2】数据结构的三要素是逻辑结构，物理结构，操作。 【3，1，2】存储结构可根据数据元素在机器中的位置是否一定连续分为顺序存储结构，链式存储结构。 【4，1，3】度量算法效率可通过时间复杂度和空间复杂度__来进行。 【5，1，3】设n 为正整数，下面程序段中前置以记号@的语句的频度是n(n+1)/2。 for (i=0; i @ k++; // 语句的频度是_____ n(n+1)/2________________。 } 【7，3，2】线性表(a1，a2，…，a n)有两种存储结构：顺序存储结构和链式存储结构，请就这两种存储结构完成下列填充：_顺序存储结构__ 存储密度较大；_顺序存储结构___存储利用率较高；_顺序存储结构___可以随机存取；_链式存储结构____不可以随机存取；__链式存储结构__插入和删除操作比较方便。 【8，3，2】从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动n-i个元素。 【9，3，2】带头结点的单链表Head为空的条件是____ Head->next==null_____ 【10，3，2】在一个单链表中p所指结点(p所指不是最后结点)之后插入一个由指针s所指结点，应执行s->next=__ p->next___;和p->next=___s _____的操作。 【11，3，2】在一个单链表中删除p所指结点时，应执行以下操作： q= p->next; p->data= p->next->data; p->next= p->next->next_ ; free(q); 【12，3，2】带头结点的单循环链表Head的判空条件是_ Head->next==null ____；不带头结点的单循环链表的判空条件是__ Head==null___。 【13，3，2】已知L是带表头结点的非空单链表, 且P结点既然不首元结点,也不是尾元结点,试从下列提供的答案中选择合适的语句序列。 a. 删除P结点的直接前驱结点的语句序列是_10 12 8 11 4 14______。 b. 删除结点P的语句序列是_____10 12 7 3 14___________。 c. 删除尾元结点的语句序列是______9 11 3 14___________。 (1) P = P->next; (2) P->next = P; 2 / 50 1、试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。 答：开始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。 链表的头指针是一指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。 头结点是我们人为地在链表的开始结点之前附加的一个结点。有了头结点之后，头指针指向头结点，不论链表否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)。 2、何时选用顺序表、何时选用链表作为线性表的存储结构为宜? 答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑： 1) 基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。 2) 基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。 3、在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素? 答：在等概率情况下，顺序表中插入一个结点需平均移动n/2个结点，删除一个结点需平均移动(n-1)/2个结点。具体的移动次数取决于顺序表的长度n以及需插入或删除的位置i。i 越接近n则所需移动的结点数越少。 4、为什么在单循环链表中设置尾指针比设置头指针更好? 答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next 和rear, 查找时间都是O(1)。 若用头指针来表示该链表，则查找终端结点的时间为O(n)。 5、在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少? 答：我们分别讨论三种链表的情况。 1) 单链表。当我们知道指针p指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。 2) 双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。 3) 单循环链表。根据已知结点位置，我们可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。 第三章习题 1. 按图3.1（b）所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答： ⑴ 如进站的车厢序列为123 ，则可能得到的出站车厢序列是什么？ ⑵如进站的车厢序列为123456 ，能否得到435612 和135426 的出站序列，并说明原因。（即写出以“S”表示 进栈、以“ X”表示出栈的栈操作序列）。 2. 设队列中有A、B、C、D、E这5个元素，其中队首元素为A。如果对这个队列重复执行下列4 步操作： 1) 输出队首元素； 2) 把队首元素值插入到队尾； 3) 删除队首元素； 4) 再次删除队首元素。 直到队列成为空队列为止，得到输出序列： （1）A、C、E、C、C （2）A、C、E （3）A、C、E、C、C、 C （4）A、C、E、C 3. 给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？ 4. 按照四则运算加、减、乘、除和幕运算（T）优先关系的惯例，画出对下列算术表达式求值时操 作数栈和运算符栈的变化过程： A — B *C/D+EfF 5. 试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1 & 序列2' 模式的字符序 列。其中序列1 和序列2 中都不含字符' &'且，序列2 是序列1 的逆序列。例如，‘a+b&b+a '是属该模式的字符序列，而’1+ 3 & 3 —1'则不是。 6. 假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将一个通常书写形式且书写正确的表达式转换 为逆波兰式。 7. 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点 (注意不设头指针) ，试编写相应的队列 初始化、入队列和出队列的算法。 8. 要求循环队列不损失一个空间全部都能得到利用,设置一个标志域tag ,以tag为0或1来区分 头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。 9. 简述以下算法的功能(其中栈和队列的元素类型均为int )： ( 1 )void proc_1(Stack S) { int i, n, A[255]; n=0; while(!EmptyStack(S)) {n++; Pop(&S, &A[n]);} for(i=1; i<=n; i++) Push(&S, A[i]); 选课了，希望大家都有好课选。这是些选课的参考，有些课有点小变化吧，别的基本没变，希望对大家可 以有点帮助！！！ 仅供参考 一、课程及老师推荐 由历届学长们的血的教训总结而出 1. 语言英语：方富民王元春吴越民熊海虹徐明陈颖朱晨晨德语：陆伸日语：张宏斌 2. 计算机计算机组成：潘学增杨起帆 数据结构：王申康陈越 操作系统：李善平 网络应用：孟炳泉 c语言：高济平王何宇白洪欢吴晓华应晶 大学计算机基础：白洪欢 vb 程序：孟炳泉 3. 理工科微积分:苏得矿吴明华龚乐春陈锦辉卢兴江吴建民景荣荣金显吴彪 大学物理：陈凤至潘正权阮晓声 physics：方本民潘正权鲍世宁大学物理：阮晓声陈凤至陆文琴 大学物理学实验：周小风陈星 有机化学：吴军吴百乐 无机及分析化学：贾之慎大学化学实验：曾秀琼 概率论：谈之奕黄柏琴吴国桢 数理统计：吴国桢 复变函数：汪国昭应文隆 线性代数：谈之奕戴佳玲单鉴华李方汪国军[何勇] 电路原理：贾爱民马佐群孙辉范承志 常微分方程：卢兴江应文隆贾厚玉薛儒英姜海益吴彪 偏微分方程：薛儒英贾厚玉 数学分析：沙震(是丘班的课，一般人不可选）李松 模拟电路：祁才君沈连丰 数字电路：沈连丰 电子技术基础：王小海 有机化学：吴军 工程图学：施岳定费少梅 画法几何：施林祥 理论力学：叶敏 应用电子学：王玉芬 4. 经管现代经济学：陈君徐林危启才盛晓明凤进 微观经济学：金祥荣章华施杰 宏观经济学：徐林叶航 经济法：丁关良 财务管理：赵静 管理心理学：林良夫 5. 生物医学生物论理学：袁康培 现代遗传学概论：石春海 普通生物学：钱凯先 生物化学：史锋 现代遗传学：石春海 医学史：郭永松 6. 公选课政治经济学：戴文标舒泽虎蒋文华廖亦宏包松王建宇李敏邓论：熊卫平绕清水章鑫强吴元耕宇正香 军事理论：吕强褚良才 毛概：许建平李立志 法律基础：龚慧香吴红瑛 马克思哲学：张应杭 思想道德修养：万慧进黄步琦 7. 限选课、校选课、院选课 化学与人类文明：谢玉群毛建新胡吉明徐冬梅 物理与人类文明：叶高翔沙健 环境与人类文明：刘广深 现代管理基础：郭红东陈随军戚振江 现代经济基础：陈君 生命科学导论：唐建军史锋 工程化学：郭永胜 大学语文：许志强黄擎陶然李力金立汪超红 大学写作：金立朱首献 中国近代军事史：姚杏民褚良才 中华人民共和国史：李立志 伦理学：张应杭朱法桢 社会学：刘玉能 天文学：刘广深 军事学和国防科技：吕强 诗歌鉴赏与写作：黄杰 风景画入门：付东黎 离散数学：王维维金小刚 心理学概论：符德江 社会心理学：王小章吴明证 美学：易容 19年浙大数据结构真题整理 -----木君,群内相关讨论及资源 数据结构： 1. 选择题 1.选出算法时间最快（）（C 其中logN与N不在一个数量级） A. O(n^2) B. O(n^3) C. O(n(log N)^4) D. O(n^3/2) 2.不是链表所具有的特性（）（A） A.可以随意查找 B.插入删除的复杂度为O(1) 3.判断栈的出栈顺序，是否正确（）（王道常见题型） 4.中序和后序的结果一样的，则该树所具有的特征（）（王道常见题型） 5.78，85，120，65，61...的序列排成AVL树，其中不正确的描述（）（该题还是AVL树的平衡） A.是一棵完全二叉树 B.x是根节点 C.其中a,b是兄弟结点 6.拓扑排序(王道) 7.进行一趟快排后，形成的新的序列（王道） 8.有2333个数的最小堆，最大值不可能在下面的哪个节点上（） A. 1113 B.1556 C…（王道，非叶子结点即可） 9.给出一张图，找出最小生成树，（王道，建议使用，kruskal算法） 10.（a,b,c,d）,a，b是最小频率使用的两个结点，不可能出现的编码（） C c:10 d:0 11.给出邻接表，判断它的深度遍历顺序（）（这题不是很会处理，感觉每个选项都像对） 12.广度搜索 13.20，25，16，7，96…….。进行一趟，排序问选择哪种（） A.堆排序 B.快排 C.二路并归 (20) 2. 简答题 1.1给定一串数，将他们排列成一棵完全二叉树，并保证该树是一棵二叉搜索树。 1.2并对上述的二叉树进行前序遍历 2.给出一个图，用dijkstra算法求最短路径，要求写出查找的序列以及距离起始点的最短距离。 3．程序填空 进行最大堆进行调整，主要是if语句的调整。（往年真题出现过） （思路）主要的if()语句的判断，判断内容属于对一个节点的左右孩子的比较，选出最大的那个孩子，以便进行下一个if的判断，对当前节点和刚刚最大的孩子的比较。 3.编程题 是将单链表进行新的排序，如123456，转变为615243，时间复杂度O(n)，空间复杂度O(1), 您的本次作业分数为：100分单选题 1.设散列表长为14，散列函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测法解决冲突，则放入的位置是____________。 A 8 B 3 C 5 D 9 正确答案:D 单选题 2.下列排序算法的时间复杂度最小的是____。 A 冒泡排序 B 希尔排序 C 简单选择排序 D 归并排序 正确答案:D 单选题 3.带头结点的单链表Head为空表的判定条件是______。 A Head->next==Head B Head->next==NULL C Head!=NULL D Head==NULL 正确答案:B 4.若用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值位于中间值的前面，下次的查找区间为从原开始位置至____。 A 该中间位置 B 该中间位置－1 C 该中间位置＋1 D 该中间位置／2 正确答案:B 单选题 5.一组记录的关键字为（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 正确答案:C 单选题 6.下面关于图的存储的叙述中，哪一个是正确的？ A 用相邻矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关 B 用相邻矩阵法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关 C 用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关 D 用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关 正确答案:A 浙江大学2009–2010学年秋学期 《数据结构基础》课程期末考试试卷(A) 课程号： 211C0020_，开课学院：_计算机科学与技术_ 考试试卷：√A卷、B卷（请在选定项上打√） 考试形式：√闭、开卷（请在选定项上打√），允许带____无___入场 考试日期： 2009 年 11 月 17 日,考试时间： 120 分钟 诚信考试，沉着应考，杜绝违纪。 考生姓名：学号：所属院系： _题序一二三四总分得分 评卷人 Answer Sheet Part I (24) 1. 2. 3. 4. 5. 6. 7. 8a. 8b. 9. 10. 11. Part II (18) 1. c______________d_________________ e_______________ f________________ 2. c_________________ d_________________ Part III (43) 1. 2. (a) The initial max-heap sequence is: (b) The sequences of the first 4 runs are: 3. (a) DFS: (b) BFS: (c) Topological order: 4. S 1 2 3 4 5 6 7 8 9 10 Union(1,2) Union(3,4) Union(1,3) Union(3,5) Union(6,7) Union(1,7) Union(7,8) Union(4,10) NOTE: Please write your answers on the answer sheet. 注意：请将答案填写在答题纸上。 I. Please select the answer for the following problems. (24 points) (1)Given as following the recurrence relations of the time complexities of two programs: P1. T(1)=1, T(N)=T(N/2)+1; and P2. T(1)=1, T(N)=2T(N/2)+1; What conclusion can be made about the time complexities of the two programs? a. both are O(logN) b. O(logN) and O(NlogN) respectively c. both are O(N) d. O(logN) and O(N) respectively (2)In a singly linked list with N nodes, which operation requires the time complexity of O(N)? a. to find the i-th node in the list （1≤i≤N） b. to insert a new node after the node pointed by p c. to arrange the nodes of the list in increasing order d. to delete a node after the node pointed by p (3)If a queue is implemented by a circular array with size m. It is given that the front element is at f and the length of the queue is s. Where is the rear element in the queue? a. f+s b. f+s-1 c. (f+s-1)%m d. (f+s)%m (4)Among the following sorting algorithms, which one has the properties that for each step at least one element can be placed to its final position and the number of comparisons is NOT related to the initial order of the list to be sorted? a. Selection sort b. sort Heap c. Quick sort d. Insertion sort (5)If quadratic probing is used, and the table size is prime, then which one of the following is true? a. A new element can always be inserted b. A new element may not be inserted c. A new element can not be inserted d. None of the above (6)To test if there is a cycle in a given digraph, which of the following method can be used besides topological sort? Breath-First-Search a. b. Depth-First-Search c. Critical Path Method d. Dijkstra Method (7)The sufficient conditions of a graph of N vertices being a tree are that the graph must be a. connected and directed b. acyclic and directed c. connected and acyclic d. containing exactly N-1 edges (8) A graph of N vertices contains at least , and at most connected components. a. 0 b. 1 c. N-1 d. N浙大远程数据结构与算法离线答案-完整版
数据结构第二章习题课
数据结构第三章习题答案解析
浙江大学课程推荐(学长学姐吐血整理)
2019年浙大数据结构真题整理
2014--浙江大学远程教育学院在线作业数据结构与算法100分
浙大数据结构期末考试2009-2010
相关主题
文本预览