当前位置：文档之家 › 数据结构与算法设计

数据结构与算法设计

  • 格式：doc
  • 大小：95.00 KB
  • 文档页数：13

1 北京理工大学现代远程教育学院2004-2005学年第一学期 《数据结构和算法设计》试卷

班级： 姓名 ： 学号 ： 成绩 ：

一、 选择(15分) 1．如果类A中定义了一个成员函数形式为void put(int)；以A类为基类的派生类中重载此函数，以下（ ）不对。 A、void put(float)； B、void put(int)； C、int put(int)； D、void put(char*);

2．如果以某个类的成员函数方式重载了运算符”/”号，a/b表达式对应的函数调用形式为（ ） A、a. operator/(b); B、operator/(a，b); C、b. operator/(a); D、operator/(b，a);

3．公有派生类的外部对象允许访问其基类（private、protected、public各域）中的( ) 域成员。 A、private B、public C、protected D、protected和public

4．Base为基类，First为其派生类，Last为First的派生类，如果定义 Base obj1，*P1； First obj2，*p2；Last obj3，*p3；以下语句非法的为（ ）； A、p1=&obj2; B、p2=&obj3; C、p3=&obj2; D、p2=&obj2;

5．如果类A中定义了一个成员函数为虚函数，其函数原型为void put(int)；以A类为基类的派生类B中，( )函数具有虚特性。 A 、void put(float)；B、int put( )；C、void put(int)；D、void put(char*);

6．高度为K的二叉树至多有（ ）个结点（K>=≥-1） A、 2k+1-1 B、 2k+1+1 C、 2k-1 D、 2k+1

7．线性链表是通过何种方式表示元素之间的关系( ) A、 后继元素地址 B、 元素的存储顺序 C、 左、右孩子地址 2

D、 元素的相对存储位置 8．数据结构在计算机中的表示是指( ) A、 数据的存储结构 B、 数据结构 C、 数据的逻辑结构 D、 数据元素

9．用线性链表存储线性表时，要求存储空间( ) A、 必须是连续的 B、 连续不连续都可以 C、 部分元素的存储空间必须是连续的 D、 必须是不连续的 .

10．若某线性表最常用的操作是在表头或表尾结点之后插入一个结点或删除一个结点，则采用哪一种存储结构算法的时间效率最高。( ) A、 单链表 B、 给出表头指针的单循环链表 C、 双向链表 D、 给出表尾指针的循环链表

11．一个栈的输入序列为m，n，p，q，则下列序列中不可能的输出序列是( )。 A、 n p q m B、 m p n q C、 q n p m D、 m q p n

12．查找效率最高的二叉排序树是( ) A、 所有结点右子树或左子树都为空的二叉排序树； B、 平衡二叉树 C、 没有左子树的二叉排序树

13．在线性表顺序存储结构下，在第i个元素之前插入新元素需要( ) A、 移动元素 B、 修改头指针 C、 队头指针 D、 申请新的结点空间

14．对于经常要存取元素的应用，线性表应采用( )存储结构。 A、 顺序存储结构 3

B、 链式存储结构 C、 线性链表 D、 栈

15．二叉排序树的（ ）遍历结果是一个有序序列。 A、中序 B、后序 C、前序 D、层次

二、 指出每个程序中的出错行号，简要说明原因并修改（25分）。 1．#include class my{ int x,y; public: ① my(int x0=10,int y0){ x=x0, y=y0;} ② void set(int x,int y){my::x=x,my::y=y;} }; main( ) { ③ my *ptr,data(10,20); ④ ptr=new my[5]; ⑤ ptr->set(3,4); ⑥ cout

2．class Fruit{ protected: int num; public: ① Fruit( ){num=0;} ② Fruit(int n=10){num=n;} ③ virtual int show( )=0; }; ④ class Apple:public Fruit{ public: ⑤ Apple(int m=10):Fruit(m){ } ⑥ void show(){cout<}; void main( ) 4

{ ⑦ Fruit fru , *ptr; ⑧ Apple x; ⑨ ptr=&x; ⑩ ptr->show(); }

3．class x{ int a; public: int set(int a0){a=a0;} int get() {return a;} void outputa() {cout<}; ① class y:x{ ② int b; public: ③ void setb(){b=a*a;} ④ void outputb() ⑤ {outputa();cout<}; void main( ) { ⑥ x *ptr; ⑦ y y1; ⑧ y1.setb(); ⑨ ptr=&y1; ⑩ ptr->outputb(); }

三、 简答题(20分) 1．已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，...，nk

个度为k的结点，问该树中有多少个叶子结点？

2．请画出图示森林对应的二叉树。 5

3．假设一棵树的后序序列为DHIEBFKLJGCA和中序序列为DBHEIAFCKJLG (1) 请画出该树 (2) 至少给定哪几种遍历结果可以唯一地确定一棵二叉树？ (3) 请写出其前序遍历的结果。

4．假设输入序列为{9，17，5，4，23，8，6，54，22}，请构造出二叉排序树，并给出此树删除23后的形状。

5．试分别找出满足以下条件的所有二叉树 (1） 二叉树的前序序列与中序序列相同 (2） 二叉树的后序序列与中序序列相同 (3) 二叉树的后序序列与前序序列相同

四、程序填空题（16分） 1．假设称正读和反读都相同的字符序列为回文，例如，’abba’和’abcba’是回文，

而’abcde’和’ababab’则不是回文，下列程序首先实现了一个简单的链栈，然后利用此栈，判别输入的字符串是否为回文，请将程序补充完整。 #include #include #include class LinkStack; class StackNode{ char data; StackNode *next; friend class LinkStack; }; class LinkStack{ protected : 6

StackNode * top; //栈顶指针 public: （1） //必要的构造函数声明 ~LinkStack() {Clear();} void Clear(); void Push(char& x); bool Pop(char&x); bool IsEmpty(){ （2） } }; //清空当前栈中元素 void LinkStack::Clear() { char x; while(Pop(x)); } //进栈函数，将x 压入链栈中 void LinkStack::Push(char& x) { StackNode *p; if(top) { p=new StackNode; assert(p); (3) (4) (5) } else { top=new StackNode; assert(top); top->data=x; top->next=NULL; } } //出栈函数，将栈顶元素弹出，并将栈顶结点的数据元素值赋给x bool LinkStack::Pop(char&x) { StackNode *p; 7

if(!IsEmpty()) //若栈中有元素 { x=top->data; (6) (7) (8) return true; } return false; } void main() { LinkStack stack; char s[20],s1[20],c; cout<<"Please input string:"; cin>>s; for(int i=0;(c=s[i])!=0;i++) (9) i=0; while((10) ) (11) s1[i]=0; if(strcmp(s1,s)==0) cout<<"Yes\n"; else cout<<"no\n"; } 2．以下程序定义了一个简单顺序队列类，请将其补充完整。 #include "iostream.h" #include "assert.h" class SeqQuene{ protected: int head; //队头指针 int tail; //队尾指针 int *elements;//存放队列元素的数组 int maxsize;//队列最大可容纳元素个数 public: SeqQuene(int i=10) { head=tail=0;

合集下载

数据结构与算法

数据结构与算法

数据结构与算法数据结构与算法是北京大学于2018年02月26日首次在中国大学MOOC开设的慕课课程，是国家精品在线开放课程。

该课程授课教师为张铭、陈斌、卢宗青、刘云淮、赵海燕、宋国杰、黄骏、邹磊、王腾蛟。

据2021年2月中国大学MOOC官网显示，该课程已开课4次。

数据结构与算法课程内容包括数据结构与抽象数据类型、算法特性及分类、算法效率与度量、线性结构、顺序表、链表、栈与队列、栈与递归、递归转非递归、字符串的存储结构、字符串运算的算法实现、字符串的快速模式匹配、二叉树的抽象数据类型、二叉树的搜索、二叉树的存储结构、树与二叉树的等价转换、树的抽象数据类型及树的遍历、树的链式存储结构、树的父指针表示法、树的顺序存储和K叉树、图的概念和抽象数据类型、图的存储结构、图的遍历、内排序、检索等内容。

课程性质:课程背景计算机是现代社会中用于解决问题的重要工具，支撑这个工具高效运转的就是其后的各种系统程序、应用程序。

数据结构，是抽象的表示数据的方式；算法，则是计算的一系列有效、通用的步骤。

算法与数据结构是程序设计中相辅相成的两个方面，是计算机学科的重要基石。

课程定位数据结构与算法是介绍基本数据结构以及相关的经典算法，强调问题-数据-算法的抽象过程，关注数据结构与算法的时间空间效率，培养学生编写出高效程序从而解决实际问题的综合能力的一门课程。

适应对象数据结构与算法适合计算机以及相关理工专业的本科生学习。

对于具有C语言结构化程序设计基础的学生，该课程第0章补充了一些面向对象的基本内容。

课程简介:数据结构与算法围绕着“算法+数据结构=程序”的思路，以问题求解为导向进行学习，运用问题抽象、数据抽象、算法抽象来分析问题，应用适当的数据结构和算法来设计和实现相应的程序。

在求解实际问题方面，该课程会学习到通过权衡时空和其他资源开销，利用数据结构来组织数据、设计高效的算法、完成高质量的程序以满足错综复杂的实际应用需要。

课程所学到的内容会被利用到计算机科学后续的各个课程中，如操作系统、软件工程、数据库概论、编译技术、计算机图形学、人机交互等。

数据结构与算法设计-习题1-3

数据结构与算法设计-习题1-3


int
data;
struct Lnode *next;
// 数据域 // 指针域
} LNode, *LinkList; LinkList la, lb； // 单链表的头指针 请用 la 和 lb 中的结点合并生成一个新的非 递增的有序单链表 lc。合并完成后，原来的 la 和 lb 成为空链表。
作者 (时间 2000年） 北京理工大学计算机科学工程系 秦怀青 email qinhq010@
正确且高效的算法如下： Status DeleteK（SqList &a ,int i, int k） {//设线性表元素从a.base[1]起存储,从第i个元素起
删除k个元素。
if ( i<1|| k< 0 || (i+k)>a.length) return ERROR;
for ( j=i+k;j<=a.length; ++j)
操作步骤
1) 建空表 Lc; 2) 依次从 La 或 Lb 中“摘取”元素值较小的
结点插入到 Lc 表中第一个结点之前直至其 中一个表变空为止; 3) 继续将 La 或 Lb 其中一个表的剩余结点插 入在 Lc 表的表头结点之后; 4) 释放 La 表和 Lb 表的表头结点。
作者 (时间 2000年） 北京理工大学计算机科学工程系 秦怀青 email qinhq010@
单链表中逻辑上相邻的元素的物理位置 不一定 紧邻。
（3）在单链表中，除了头结点外，任一结点的存储位置 由 该结点的直接前趋 指示。
（4）在单链表中设置头结点的作用是
在表的第一个元素结点之前插入新元素结点或删除 第一个元素结点不需修改头作指者 针(时间 2000年）
数据结构与算法 c语言

数据结构与算法 c语言

数据结构与算法 c语言（一）数据结构数据结构是指程序中使用的数据存储和组织的方式，是存储和组织数据以便于进行有效访问和操作的形式。

它们描述如何组织、索引、检索和存储数据，可以以图形、列表、树或任何其他形式来实现。

根据它的功能，数据结构可以分为三类：存储结构，查找结构和排序结构。

1.存储结构：存储结构定义数据的存储形式，结构的类型有线性结构、非线性结构和特殊结构。

a）线性结构：线性结构是最常用的存储结构，常见的线性结构有数组、线性表和栈。

b）非线性结构：非线性结构是存储数据的不规则结构，常用的非线性结构有森林、图、哈希表和布局。

c）特殊结构：特殊结构是一种特殊的数据结构，代表着不同的操作对象。

例如，编译器存储着源程序的语法树,在设计数据库时,系统存储着索引树以及索引文件。

2.查找结构：查找结构包括线性查找和二分查找，前者将数据成员与关键字一一比较，后者使用二叉树技术，在减少比较次数的同时，使得查找效率大大提高。

3.排序结构：排序结构按照一定的规则对存储在某个存储结构中的数据进行排序，用于快速查找数据。

常用的排序算法有插入排序、合并排序、快速排序等。

总之，数据结构可以视为数据的容器，使用不同的数据结构可以解决不同的问题，提高系统的效率。

（二）算法算法是一种排列和组合的解决问题的过程。

它使用一组定义明确的步骤，按照该步骤来执行，最终解决问题。

一般来说，算法分为三种类型：贪心算法、动态规划和分治法。

1.贪心算法：贪心算法通过采用试探性选择来求解问题，它从不考虑过去的结果，而是假设采用当前最好的结果，从而得到最优解。

如择优法、多项式时间的算法都属于贪心算法。

2.动态规划：动态规划是求解决策过程最优化的数学术语，它结合搜索技术，用最优方式选择最佳决策。

常见的动态规划算法应用有最小路径求解，最优工作调度等。

3.分治法：分治法是算法设计中比较常用的思想，它的思想很简单，就是将问题分解成多个子问题，分别解决，最后合并解决结果，得到整体的问题的最优解。

数据结构与算法实验报告

数据结构与算法实验报告

《数据结构与算法》综合实验报告系别：专业：学生姓名：指导教师：2011年 11月 25日实验目的掌握线性表的建立、插入、删除算法；掌握查找算法；掌握排序算法；实验要求使用C语言（环境任意）开发程序，能够对用户输入的任意一组数据，建立一个线性表，可以输出此线性表。

并且能够对此线性表进行插入、删除、查找、排序等操作。

程序流程建表如下：定义一个整型的数据类型data和next指针：定义头指针和当前结点指针，申请连续空间将单个字节大小复制给头指针，把头指针赋值给当前节点指针：若输入的数是0，则若输入不为0，把输入的数赋值给已申请的新结点，把新结点赋给当前节点的next域，再把新结点赋值给当前结点，以此方法重复执行得到如下链表：输出函数：把头指针赋值给当前结点指针，当当前节点的next域不为空时输出当前节点所指向的数据，把当前结点的next域赋值给当前节点，否则输出链表为空对此线性表进行插入、删除、查询、排序操作把已申请的结点数据域指向所输入的数再把插入w结点赋值头结点，是插入的位置，如果w=0则插入结点的next域赋值给头结点否则如果w>表长，则输出超出范围代码及运行结果（主要语句要求有注释）#include"stdafx.h"#include<stdio.h>#include<malloc.h>#define NULL 0typedef struct linknode{int data;struct linknode *next;}node;node *head;node *creat(){node *currnode,*newnode;int x;head=(node*)malloc(sizeof(node));currnode=head;do{scanf("%d",&x);newnode=(node*)malloc(sizeof(node));newnode->data=x;currnode->next=newnode;currnode=newnode;}while(x!=NULL);head=head->next;currnode->next=NULL;return head;};int length(){node *currnode;int i=0;currnode=head;while(currnode->data!=NULL){currnode=currnode->next;i++;};return i;};void print(){node *currnode;currnode=head;printf("链表如下....linklist");while(currnode->data!=NULL){printf("%d-->",currnode->data);currnode=currnode->next;};printf("NULL\n");printf("链表长度为........linklist length%d\n",length());};void delete1(){int x;node *delnode,*currnode;printf("输入要删除的数据......input delete data：");scanf("%d",&x);if(head->data==NULL) printf("此链表为空无法删除.....this linklist empty！\n"); if(head->data==x){delnode=head;head=head->next;free(delnode);if(head==NULL) printf("此链表为空.......this linklist enpty！");}else{currnode=head;delnode=currnode->next;while(delnode->data!=x&&delnode!=NULL){currnode=currnode->next;delnode=currnode->next;};if(delnode==NULL)printf("无此数据......no this data！\n");else{currnode->next=delnode->next;free(delnode);};};};void find(){node *currnode;int count=1,x;currnode=head;printf("输入要查找的数据.......input search data:");scanf("%d",&x);while(currnode->data!=NULL&&currnode->data!=x) {currnode=currnode->next;count++;};if(currnode->data!=NULL){printf("\n%d为第........is no.",currnode->data);printf("%d个数据........data。