数据结构和算法

一.选择题（共15题，每题3分）

（1）下面关于算法说法错误的是_______。 a. 算法最终必须由计算机程序实现

b. 为解决某问题的算法同为该问题编写的程序含义是相同的 c. 算法的可行性是指指令不能有二义性 d. 以上几个都是错误的 （2）下面说法错误的是______.

a. 算法原地工作的含义是指不需要任何额外的辅助空间

b. 在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 c. 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 d. 同一个算法，实现语言的级别越高，执行效率就越低 （3）在下面的程序段中，对x的赋值语句的频度为_____。 for (int i; i

a. 0(2n) b. 0(n) c. 0(n2) d. O(log2n) （4）下面说法正确的是______。 a. 数据元素是数据的最小单位； b. 数据元素是数据的最小单位；

c. 数据的物理结构是指数据在计算机内的实际存储形式 d. 数据结构的抽象操作的定义与具体实现有关 （5）下面说法正确的是_______。

a. 在顺序存储结构中，有时也存储数据结构中元素之间的关系 b. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高

c. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立 d. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构 （6） 下述_____是顺序存储结构的优点。 a. 存储密度大 b. 插入运算方便 c. 删除运算方便

d. 可方便地用于各种逻辑结构的存储表示

（7）下面关于线性表的叙述中，错误的是_____。 a. 线性表采用顺序存储，必须占用一片连续的存储单元 b. 线性表采用顺序存储，便于进行插入和删除操作 c. 线性表采用链接存储，不必占用一片连续的存储单元 d. 线性表采用链接存储，便于插入和删除操作

（8） 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用_______存储方式最节省时间。

a. 顺序表 b. 双链表 c. 带头结点的双循环链表 d. 单循环链表 （9）静态链表中指针表示的是______。

a. 内存地址 b. 数组下标 c. 下一元素地址 d. 左、右孩子地址 （10）下面的叙述不正确的是_______。

a. 线性表在链式存储时，查找第i个元素的时间同i的值成正比 b. 线性表在链式存储时，查找第i个元素的时间同i的值无关 c. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 d. 线性表在顺序存储时，查找第i个元素的时间同i的值无关 （11）下面说法错误的是_____。

a. 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。

b. 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。 c. 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。 d. 静态链表就是一直不发生变化的链表。

（12）在双向链表指针p的结点前插入一个指针q的结点操作是______。 a. p->Llink=q; q->Rlink=p; p->Llink->Rlink=q; q->Llink=q； b. p->Llink=q; p->Llink->Rlink=q; q->Rlink=p; q->Llink=p->Llink; c. q->Rlink=p; q->Llink=p->Llink; p->Llink->Rlink=q; p->Llink=q; d. q->Llink=p->Llink; q->Rlink=q; p->Llink=q; p->Llink=q; （13）下面说法正确的是______。

a. 顺序存储结构的主要缺点是不利于插入或删除操作；

b. 线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的； c. 顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好； d. 顺序存储方式只能用于存储线性结构。 （14）下面说法正确的是______。 a. 线性表只能用顺序存储结构实现。

b. 为了很方便的插入和删除数据，可以使用双向链表存放数据。 c. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

d. 链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。 （15）下面说法正确的是_________。 a. 数据元素是数据的最小单位。

b. 队列逻辑上是一个下端口和上端能增加又能减少的线性表。 c. 任何一个递归过程都可以转换成非递归过程。

d. 只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈。 二. 填空题(共5题，每题5分)

（1） 下列程序的功能是创建单向链表，请补充完整。 #include #include struct link { char name[10]; int mark; struct link * next;

};

void insert(char * name, int mark); struct link * head = NULL; main()

{ char name[10]; int mark; struct link *t; while (1)

{ scanf(“%s %d”, name, &mark); if (strcmp(name, “#”) == 0 ) { break; }

______(1)_______; }

for (t=head; ______(2)_______) {

printf(“<%s>: %d\\n”, t->name, t->mark); } }

void insert(char * name, int mark) {

struct link * p;

p = ______(3)_______ ; strcpy(p->name, name); p->mark = mark; ______(4)_______; if ( head != NULL ) {

______(5)_______; } head = p; }

（2） 用循环链表表示的队列长度为n， 若只设头指针,则出队和入队的时间复杂度分别是______和_____； 若只设尾指针,则出队和入队的时间复杂度分别是_____和_____。 （3） 在n个记录的有序顺序表中进行折半查找,最大的比较次数是______。 （4） 仔细阅读下列程序，在空白处填入适当的语句。

函数match(s,t)完成在字符串s中寻找与t匹配的字符，若存在一个匹配，则返回t在字符串s中的下标；否则，返回-1。其中，字符指针*b始终指向s的第一元素。 Match(s,t) Char s,t; ｛ char *b=s; char *p, *r;

for _________________________________ ｛

for (p=s, r=t; *r!=`\\0` && *p= =*r; p++, r++); if__________________________________ return(s-b); ｝ return(-1); ｝

（5） 补充下列程序：设一棵二叉序列树b，下列算法函数是实现在b中插入一个结点s。 函数：

void insert（btree *b，btree *s） { if（b == NULL） b = s； else

if（s->data == b->data） return(); else

if(s->data < b->data) ； else ； }

三.简答题（共3题，每题10分）

（1） 在一个包含 n 个元素的数组 M 中查找一个元素 x。 算法假设 M 已经按升序排列了，请写出二分搜索算法的步骤。

（2） 试将一个无序的线性表A=(11,16,8,5,14,10,38,23)转换成一个按升序排列的有序线性表（用链表实现）。

（3） 何为栈和队列？简述两者的区别和联系。

一. 选择题（共15题，每题3分。）

（ 1）在C语言中, char型数据在内存中的存储形式是_____。 a. 补码 b. 反码 c. 原码 d. ASCII码

（2）设C语言中,一个int型数据在内存中占2个字节,则unsigned int型数据的取值范围为______。 a. 0～255 b. 0～32767 c. 0～65535 d. 0～2147483647 （3）已知ch是字符型变量,下面不正确的赋值语句是____。 a. ch=?a+b?; b. ch=?\\0′; c. ch=?7′+?9′; d. ch=5+9; （4）已知ch是字符型变量,下面正确的赋值语句是____。 a. ch= ?123′; b. ch= ?\\xff?; c. ch= ?\\08′; d. ch=”\\”; （5）以下选项中不正确的整型常量是_____。 a.12L b. -10 c. 1,900 d. 123U

（6）假设int型变量占两个字节的存储单元，若有定义： int x[10]={0,2,4};

则数组x在内存中所占字节数为______。 a. 3 b. 6 c. 10 d. 20

（7）C语言中能用八进制表示的数据类型为_____。 a. 字符型、整型 b. 整形、实型

c. 字符型、实型、双精度型 d. 字符型、整型、实型、双精度型 （8）以下只有在使用时才为该类型变量分配内存的存储类说明是____。 a. auto和static b. auto和register c. register和static d. extern和register

（9）下面四个选项中,均是合法整型常量的选项是____。 a. 160 b. 0xcdf c. 01 d. 0x48a 0xffff 01a 986,012 2e5 011 0xe 0668 0x

（10）下面四个选项中,均是不合法的整型常量的选项是____。 a. 0f1 b. 0Xcdf c. 018 d. 0x48eg 0xffff 017 999 068 0011 12,456 5e2 03f

（11）下面四个选项中,均是不合法的浮点数的选项是____。 a. 160. b. 123 c. 18 d. e3

0.12 2e4.2 123e4 .234 e3 .e5 0.0 1e3

（12）下面四个选项中,均是合法浮点数的选项是____。 a. +le+1 b. 60. c. 123e d. e3 5e-9.4 12e-4 1.2e-.4 .8e4 03e2 8e5 +2e 5.e

（13）下面四个选项中,均是合法转义字符的选项是____。 a. ?\\” b. ?\\? c. ?\\018′ d. ?\\\\0′ ?\\\\? ?\\017′ ?\\f? ?101′ ?\\n? ?\\”? ?xab? ?xlf?

（14）下面四个选项中,均是不合法的转义字符的选项是____。 a. ?\\” b. ?\\1011′ c. ?\\011′ d. ?\\abc? ?\\\\? ?\\? ?\\f? ?\\1011′ ?\\xf? ?\\a? ?\\}? ?xlf? （15）下面正确的字符常量是____。 a. “a” b. ?\\\\” c. ?W? d. ” 二．填空题（每题6分）。 （1）说明下面变量的定义：

char (*p[])(); _____________________ char *p()[]; _____________________ char (*p)[10][10]; _____________________ char(*(*p())[])[]; _____________________ （2）下面共同体的存储空间是_____ union BOOKNUMBER {

T_S16 age; T_S8 title[10]; T_S8 post[32]; }

（3）若整数值范围是 -32768 至 32767。在执行下面的表达式之后, i 的结果是什么? int i=32766; i=i+1; i = i=i+1; i =

（4）对于联合类型： union x {

char ch[7]; int i[2]; float f; }tom;

那么, sizeof(tom) =

（5）有以下程序，程序的输出结果是______（注意: ch[0]在低字节,ch[1]在高字节）。 #include union pw { int i; char ch[2]; }a; main() {

a.ch[0] = 13; a.ch[1] = 0; printf(“%d\\n”, a.i); }

三.简单题（共3题，每题10分）

（1）已知a为整数，比较下面代码的效率并说明原因： a++; a = a+1;

（2）已知a为整数，比较下面代码的效率并说明原因： a = a*4; a << 2;

（3）说明一个变量和定义一个变量有什么区别?

一. 选择题（共15题，每题3分。） （1）设有以下语句: char a=3, b=6, c; c = a^b<<2;

则c的二进制值是_____。 a. 00011011 b. 00010100 c. 00011100 d. 00011000

（2）表达式0×13&0×17的值是___。 a. 0×17 b. 0×13 c. 0xf8 d. 0xec

（3）表达式0xl3|0xl7的值是____。 a. 0×13 b. 0×17 c. 0xE8 d. 0xc8

（4） 以下叙述中正确的是_____。 a. 表达式a&＝b等价于a＝a&b b. 表达式a|＝b等价于a＝a|b c. 表达式a!＝b等价于a＝a!b d. 表达式a^＝b等价于a＝a^b

（5） 运作对象必须是整型数的运算符是_____。 a. % b. . c. / d. **

（6） 根据以下定义，错误的表达式是_____。 struct { int a; char b; } Q, *p = &Q; a. Q.a b. (*p).b c. p->a d. *p.b

（7） 若x是单精度实型变量，表达式 x = 10/4 的值是_____ 。 a. 2.5 b. 2.0 c. 3 d. 2 （8） 表达式 !x 等价于_____。

a. x == 0 b. x == 1 c. x != 0 d. x != 1 （9） ______是合法的用户自定义标识符。 a. b-b b. float c. d. _isw

（10） 若变量已正确定义并赋值，表达式______不符合C语言语法。 a. a*b/c; b. 3.14%2 c. 2, b d. a/b/c （11） _____是不正确的字符常量。 a. ?\\n? b. ?1′ c. “a” d. ?\\101′ （12） 在 C 程序中，用_____表示逻辑值”真”。

a. 1 b. 非 0 的数 c. 非 1 的数 d. 大于 0 的数 （13） ______把x、y定义成float类型变量，并赋同一初值3.14。 a. float x, y=3.14; b. float x, y=2*3.14; c. float x=3.14, y=x=3.14; d. float x=y=3.14;

（14） 假设变量已正确定义，表达式______的值不是2。 a. 2&3 b. 1<<1 c. a==2 d. 1^3

（15） 若变量已正确定义，语句if(a>b) k=0; else k=1;和______等价。 a. k=(a>b)?1:0; b. k=a>b; c. k=a<=b; d. a<=b ? 0 : 1; 二．填空题（每题5分）。

（1） &运算符作为单目运算符时表示的是____运算；作为双目运算符时表示的是_____运算。 （2） 请计算sizeof的值： char str[] = “Hello” ; char *p = str ; int n = 10; 请计算

sizeof (str ) = ____ sizeof ( p ) = _____ sizeof ( n ) = ______

（3） 请计算sizeof的值： void Func ( char str[100]) { // 请计算

sizeof( str ) = _____ }

（4） 请计算sizeof的值： void *p = malloc( 100 ); // 请计算

sizeof ( p ) = ______

（5） 下列程序段的输出是_______。 #define f(a, b, x) a*x+b

printf(“%d, %d\\n”, f(3,2,1), f(6, 5, f(3, 2, 1))); （6） 下列程序段的输出是_____。 main() { int k;

for(k=1; k<5; k++) {

if(k % 2) printf(“*”); else continue; printf(“#”); }}

三.简单题（共3题，每题10分） （1） 指出下面程序的错误并改正： void main(void) {int a,b; a = 1; b = a/++a;

printf(“b equals %d\\n”, b);}

（2） int a=391,b=1971; 写出 a^b^a的值。

（3） 语句：x++;?++x; x=x+1;?x=l+x; ，执行后都使变量x中的值增1，请写出一条同一功能的赋值语句。

嵌入式开发

1、 解释C语言关键字extern、static的含义。 2、 解释C语言关键字volatile、const的含义。 3、举例说明typedef和define的用法。

4、语句for( ；1 ；)有什么问题？它是什么意思？ 5、do……while和while……do有什么区别？ 6、请写出下列代码的输出内容 #include main() {

int a,b,c,d; a=10; b=a++; c=++a; d=10*a++;

printf(“b，c，d：%d，%d，%d”，b，c，d）; return 0; } 答：

7、设有以下说明和定义：（32位编译器情况下） typedef union {long i; int k[5]; char c;} DATE; struct data { int cat; DATE cow; double dog;} too;

DATE max;

则语句 printf(“%d”,sizeof(struct date)+sizeof(max));的执行结果是：_______ 8、下面是51单片机最小系统电路图，试分析该电路结构以及实现原理？

9、谈谈汇编语言、C和C++三种语言在嵌入式开发中的区别和特点？简述你对嵌入式概念的理解？ 10、列举常见的嵌入式操作系统和单片机？简要介绍你以前做过的项目，在项目中用过什么处理器和操作系统，实现什么功能以及关键技术。

本文来源：https://www.bwwdw.com/article/t3v2.html